평범한 배낭 2

아주 평범한 배낭을 다루는 두 번째 문제다.

민호는 캠프에 가려고 가방을 싼다. 가방에 어떤 물건을 넣는지에 따라 민호의 만족도가 달라진다. 집에 있는 물건을 모두 넣으면 만족도가 가장 커지지만, 민호가 들 수 있는 가방의 무게가 정해져 있어서 그 무게를 넘기도록 담을 수는 없다.

집에는 같은 물건이 여러 개 있을 수 있어서 한 종류를 두 개 이상 담는 것도 가능하다. 물건은 쪼갤 수 없고, 각 종류는 집에 있는 개수까지만 담을 수 있다.

민호가 만족도를 가장 크게 느낄 수 있는 경우를 찾아보자.

첫째 줄에 N과 M이 공백을 사이에 두고 주어진다 ($1 \le N \le 100$, $1 \le M \le 10000$). N은 민호의 집에 있는 물건의 종류 수이고, M은 민호가 들 수 있는 가방의 최대 무게다.

둘째 줄부터 N개의 줄에 걸쳐 집에 있는 물건의 정보가 한 줄에 하나씩 주어진다. 각 줄은 V, C, K로 이루어진다 ($1 \le V \le M$, $1 \le C, K \le 10000$, $1 \le V \times K \le 10000$). V는 물건 하나의 무게, C는 그 물건 하나를 가방에 넣을 때 올라가는 만족도, K는 집에 있는 그 물건의 개수다.

최대 무게를 넘기지 않게 물건을 담았을 때 민호가 느낄 수 있는 만족도의 최댓값을 한 줄에 출력한다.