Mileage Course Registration

Interview

Time limit1sMemory limit128 MB

Summary

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.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

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 $m$ 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 $n$ and Seongjun's mileage $m$ ( $1 \le n \le 100$ , $1 \le m \le 100$ ).

Two lines follow for each course. The first line contains the number of students $P_i$ who already applied to that course and its capacity $L_i$ ( $1 \le P_i \le 100$ , $1 \le L_i \le 100$ ). The second line contains the points those $P_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.

Examples5

Example 1

Input

5 76
5 4 
36 25 1 36 36
4 4
30 24 25 20
6 4
36 36 36 36 36 36
2 4
3 7
5 4
27 15 26 8 14

Expected output

Example 2
Input
```
1 1
1 2
36
```
Expected output
```
1
```
Example 3
Input
```
1 35
1 1
36
```
Expected output
```
0
```
Example 4
Input
```
3 100
2 1
36 36
3 1
36 1 2
1 1
36
```
Expected output
```
2
```
Example 5
Input
```
1 20
3 2
20 20 20
```
Expected output
```
1
```