#2414 오케스트라

24  1 s   128 MB  

Description

오케스트라의 단장을 맡은 진우는 큰 고민에 빠졌습니다. 다가올 연주회를 위하여 악기별 객원들을 초청하기로 하였지만, 한정된 예산 때문에 생각해뒀던 모든 객원을 초청할 수가 없기 때문입니다.

따라서 한정된 예산으로 최대한의 만족도를 채우기 위하여 객원을 초청하는 방법을 구해야 합니다. 각 악기의 경우 객원 초청 비용이 다르며 초청된 인원에 따른 만족도도 역시 차이가 있습니다.

Sample Input을 표현한 객원 초청 비용과 만족도의 표
악기 인당 초청비용 1인 초청시 추가 만족도 2인 초청시 추가 만족도 3인 초청시 추가 만족도
호른 50 10 5 7
팀파니 70 20 초청 불가능 초청 불가능
플루트 50 9 8 초청 불가능

예를 들어 위의 표와 같이 호른의 경우 1명의 객원을 초청하는데 50의 예산이 필요하며 최대 3명 초청 가능하다고 하면, 한 명의 경우 10의 만족도를 얻을 수 있습니다.

만약 두 명의 호른 객원을 초청할 경우 한 명의 객원을 초청했을 때의 만족도와, 5의 만족도를 추가하여 총 15의 만족도를 얻을 수 있습니다. 그리고 세 명의 객원을 초청할 경우 추가로 7의 만족도를 선사하여 150의 예산을 이용해 총 22의 만족도를 얻을 수 있습니다. 또 다른 예로 팀파니의 경우 1명의 객원을 초청하는데 70의 예산이 필요하며 최대 1명 초청 가능합니다. 한 명의 팀파니 객원을 초빙할 경우 70의 예산을 소비하여 20의 만족도를 얻을 수 있습니다.

표와 같이 각 악기별 객원의 초청비용과 인원수에 따른 만족도가 주어질 때, 오케스트라에서 얻을 수 있는 최대 만족도를 구하는 프로그램을 작성하세요. 단, 모든 악기별 객원을 초청할 필요는 없습니다.

Input

첫째 줄에는 객원을 초청할 악기의 수 $N( 1 \leq N \leq 100)$ 과 오케스트라 예산 $M(0 \leq M \leq 10,000)$이 주어집니다.

둘째 줄부터 $N$개의 줄에 걸쳐 각 악기별 객원의 정보가 주어집니다. 각 줄의 처음에는 객원 초청 비용이 주어지며, 공백 다음 최대 초청할 수 있는 객원의 수가 주어집니다. 그 뒤에는 객원이 추가 될 때마다 얻을 수 있는 만족도가 입력됩니다.

각 악기 별 객원의 수는 10명을 넘지 않으며 각 만족도는 100을 넘지 않습니다. 모든 입력은 0이상의 정수로 주어집니다.

Output

획득할 수 있는 오케스트라의 최대 만족도를 출력합니다.

Sample Input

Sample Output

3 170
50 3 10 5 7
70 1 20
50 2 9 8
39

Sample Input 2

2 100
100 1 50
50 2 10 10

Sample Output 2

50

Source

SHAKE! 예선대회