마일리지 수강신청

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 과목 경쟁자의 점수와 정원을 보고 동점 승리 조건으로 과목당 1부터 36점을 써서 m점으로 가장 많은 과목을 수강합니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

연세대학교 수강신청이 마일리지 제도로 바뀌었다. 학생은 듣고 싶은 과목마다 마일리지를 1 이상 36 이하로 걸고, 모두가 분배를 마치면 과목마다 마일리지를 많이 건 순서대로 수강인원만큼 신청을 받아들인다.

성준이는 지난 수강신청에 실패해 휴학까지 했다. 이번에는 반드시 성공하려고 학교 홈페이지를 뚫었고, 그래서 다른 학생이 이미 건 마일리지를 모두 볼 수 있다. 성준이가 마일리지를 건 뒤에 새로 신청하는 학생은 없다. 마일리지가 같으면 성준이가 앞선다.

성준이가 가진 마일리지 $m$ 을 나누어 걸어 최대 몇 과목을 신청할 수 있는지 구하라. 신청하는 과목에는 1 이상 36 이하의 마일리지를 걸어야 하고, 신청하지 않는 과목에는 마일리지를 걸지 않는다.

입력

첫째 줄에 과목 수 $n$ 과 성준이가 가진 마일리지 $m$ 이 주어진다. ( $1 \le n \le 100$ , $1 \le m \le 100$ )

이어서 과목마다 두 줄이 주어진다. 첫째 줄에는 그 과목에 이미 신청한 학생 수 $P_i$ 와 수강인원 $L_i$ 가 주어진다. ( $1 \le P_i \le 100$ , $1 \le L_i \le 100$ ) 둘째 줄에는 그 $P_i$ 명이 건 마일리지가 공백으로 구분되어 주어지며, 각 값은 1 이상 36 이하이다.

출력

첫째 줄에 성준이가 가진 마일리지로 신청할 수 있는 과목 수의 최댓값을 출력한다.

예제5

예제 1

입력

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

예상 출력

예제 2
입력
```
1 1
1 2
36
```
예상 출력
```
1
```
예제 3
입력
```
1 35
1 1
36
```
예상 출력
```
0
```
예제 4
입력
```
3 100
2 1
36 36
3 1
36 1 2
1 1
36
```
예상 출력
```
2
```
예제 5
입력
```
1 20
3 2
20 20 20
```
예상 출력
```
1
```