물류 회사의 선장인 정올이는 화물선에 대량의 상품을 싣고 무역 항해를 떠나려고 한다.

화물선에는 최대 \(M\) 무게만큼의 화물만 적재할 수 있는 엄격한 제한이 있다.

창고에는 총 \(N\) 종류의 상품들이 보관되어 있다. 각 상품 종류 \(i\)는 한 개당 \(V_i\)의 무게를 차지하고, 선적했을 때 \(C_i\)만큼의 가치를 창출한다.

또한 각 상품 종류는 창고에 무한히 많은 것이 아니라, 준비된 수량이 정확히 \(K_i\)개씩만 존재한다.

정올이는 화물선의 최대 적재 무게 제한 \(M\)을 초과하지 않으면서, 선택하여 실은 상품들의 총 가치의 합을 최대화하고자 한다.

동일한 종류의 상품은 준비된 수량 \(K_i\)개 이하로 몇 개든 나누어 실을 수 있다.

화물선에 실을 수 있는 상품들의 최대 가치 합을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 창고에 있는 상품 종류의 수 \(N\)과 화물선의 최대 적재 무게 \(M\)이 공백을 사이에 두고 주어진다.

둘째 줄부터 \(N\)개의 줄에 걸쳐 각 상품의 정보인 세 정수 \(V_i, C_i, K_i\)가 공백을 사이에 두고 주어진다.

이는 \(i\)번째 상품 한 개의 무게가 \(V_i\), 가치가 \(C_i\), 창고에 보유한 수량이 \(K_i\)개임을 의미한다.

출력

화물선의 제한 무게를 넘지 않으면서 확보할 수 있는 상품들의 최대 가치를 한 줄에 출력한다.

제한사항

• \(1 \le N \le 100\)
• \(1 \le M \le 10,000\)
• \(1 \le V_i \le M\)
• \(1 \le C_i \le 1,000\)
• \(1 \le K_i \le 10,000\)

예제 입력 1

2 3
2 3 2
3 5 1

예제 출력 1

5

예제 입력 2

3 10
2 5 3
3 8 2
4 12 2

예제 출력 2

29