책 도둑

문제 정보

문제

책방에 책 도둑들이 들었다. 책도둑들은 책방의 모든 책들을 크기와 값어치에 따라 N종류로 분류했다.(한 종류의 책이 여러 권 있을 수 있다.) 책도둑들이 준비한 자루의 크기가 V일 때, 최대로 가능한 훔칠 수 있는 값어치를 알아보자.

입력

첫 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 첫 줄에는 책의 종류 N(1 ≤ N ≤ 100)과 자루의 크기 V(1 ≤ V ≤ 10,000)이 주어진다. 그 뒤 N개의 줄에는 각각 책 종류별 크기, 값어치, 개수를 나타내는 세 개의 숫자 vi,ci,ki (1 ≤ vi ≤ V, 1 ≤ ci ≤ 10,000, 1 ≤ ki ≤ 10,000, 0 ≤ i < N, 단 1 ≤ vi* ki ≤ V)가 주어진다.

출력

각 테스트 케이스마다 훔칠 수 있는 최고 값어치를 출력한다.

예제 입력

1
3 100
50 100 2
40 100 1
2 1 50

예제 출력

205

노트

8개의 댓글이 있습니다.