====== Yonsei TOTO ======

===== 풀이 =====
  * 수강하기 위해서 적은 마일리지가 필요한 과목부터 신청하면 된다
  * 각 과목의 필요한 마일리지는, 다른 사람들이 신청한 마일리지들중 L번째로 큰 값이다 (L=수강인원). 그러면 딱 L등으로 수강이 가능하다
    * 신청한 사람이 수강인원보다 적을때는, 1만큼만 마일리지를 내면 된다
  * 모든 과목에 대해서 필요한 마일리지를 구했으면, 작은 순으로 정렬한 다음에 가능한 많이 신청하면 된다.
  * 각 과목의 마일리지를 얻기 위해서는 신청한 사람들의 마일리지를 정렬해야 하니까, n * O(plogp) = O(nplogp) 이 걸리고, 최종적으로 과목별로 필요한 마일리지를 정렬해야 하니까 O(nlogn)이 걸려서, 총 O(n*(logn + plogp))가 걸린다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12018. Yonsei TOTO".

- Problem link: https://www.acmicpc.net/problem/12018
- Solution link: http://www.teferi.net/ps/problems/boj/12018

Tags: [greedy]
"""


def main():
    n, m = [int(x) for x in input().split()]
    required_mileages = []
    for _ in range(n):
        P, L = [int(x) for x in input().split()]
        mileages = [int(x) for x in input().split()]
        if L > P:
            required_mileages.append(1)
        else:
            required_mileages.append(sorted(mileages, reverse=True)[L - 1])

    answer = 0
    for rm in sorted(required_mileages):
        if m < rm:
            break
        m -= rm
        answer += 1

    print(answer)


if __name__ == '__main__':
    main()

</dkpr>


{{tag>BOJ ps:problems:boj:실버_3}}