비디오 게임 고민

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

요약

각 콘솔은 최대 하나, 게임은 해당 콘솔을 산 경우에만 살 수 있다는 조건에서 예산 V 안에서 생산 가치 합의 최댓값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

농부 존의 소들은 비디오 게임을 아주 좋아합니다! 존은 소들이 게임을 하고 나면 평소보다 훨씬 많은 우유를 만들어 낸다는 사실을 알아챘습니다. 만족한 소가 더 많은 우유를 만드는 것이 분명합니다.

그런데 소들은 어떤 게임기가 가장 좋은지를 두고 의견이 엇갈립니다. 존은 소들이 우유를 가장 많이 생산하도록 게임기와 게임을 사 주려고 합니다. 각 게임기는 종류별로 최대 한 대까지, 각 게임도 종류별로 최대 하나까지만 살 수 있으며, 전체 지출은 정해진 예산을 넘길 수 없습니다.

게임기는 모두 $N$ 종류가 있습니다. $i$ 번째 게임기는 가격 $P_i$ 를 가지며, 그 게임기에서만 즐길 수 있는 전용 게임이 $G_i$ 개 있습니다. 어떤 게임을 사려면 반드시 먼저 그 게임 전용 게임기를 소유해야 합니다. 각 게임 $j$ 는 가격 $GP_j$ 와 생산값 $PV_j$ 를 가지며, 생산값은 그 게임을 한 소가 만들어 내는 우유의 양을 뜻합니다. 존이 쓸 수 있는 최대 금액은 $V$ 입니다.

존이 예산 안에서 사들인 게임들의 생산값 합을 최대로 만드세요.

제약 조건

$1 \le N \le 50$
$1 \le P_i \le 1000$
$1 \le G_i \le 10$
$1 \le GP_j \le 100$
$1 \le PV_j \le 1{,}000{,}000$
$1 \le V \le 100{,}000$

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $V$ .
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄은 $i$ 번 게임기의 정보로, 게임기 가격 $P_i$ , 전용 게임 수 $G_i$ , 그리고 $G_i$ 개의 정수 쌍 $GP_j\ PV_j$ (게임 가격과 생산값)가 차례로 주어집니다.

출력

존이 예산 안에서 얻을 수 있는 생산값 합의 최댓값을 한 줄에 출력합니다.

예제3

예제 1

입력

3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

예상 출력

예제 2
입력
```
1 400
300 3 30 50 40 80 20 30
```
예상 출력
```
160
```
예제 3
입력
```
2 1000
300 1 50 100
400 1 50 200
```
예상 출력
```
300
```