Mileage Course Registration

Given each course rival bids and capacity, bid 1 to 36 points per chosen course, winning ties, to take the most courses with m points.

Medium4GreedySortingInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

Yonsei University switched course registration to a mileage system. Each student puts 1 to 36 mileage points on every course they want, and once everyone has finished, each course admits applicants in decreasing order of the points they put, up to the capacity of the course.

Seongjun failed the last registration and took a leave of absence, so this time he broke into the school website. He can now see every point the other students have already put. Nobody registers after Seongjun puts his own points, and a tie goes to Seongjun.

Seongjun has mm mileage points. Find the largest number of courses he can get into. He must put between 1 and 36 points on a course he applies to, and he puts nothing on a course he skips.

Input

The first line contains the number of courses nn and Seongjun's mileage mm (1n1001 \le n \le 100, 1m1001 \le m \le 100).

Two lines follow for each course. The first line contains the number of students PiP_i who already applied to that course and its capacity LiL_i (1Pi1001 \le P_i \le 100, 1Li1001 \le L_i \le 100). The second line contains the points those PiP_i students put, separated by spaces. Each value is between 1 and 36.

Output

Print the largest number of courses Seongjun can register for with his mileage.