비디오 게임 고민

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

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

게임기는 모두 $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$(게임 가격과 생산값)가 차례로 주어집니다.

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