배낭
시간 제한1초메모리 제한512 MB
가치, 무게, 개수가 주어진 N가지 물건을 무게 S 이내로 골라 총가치를 최대로 만드는 개수 제한 배낭 문제다.
문제
어느 주부가 백화점에서 "장바구니가 넘치지 않는 한 무료로 쇼핑"이라는 상품에 당첨되었다.
이 주부는 최대 S킬로그램까지 담을 수 있는 장바구니를 받았다.
백화점에는 N종류의 물건이 있고, i번째 물건의 가치는 Vi SGD, 무게는 Wi킬로그램이며, 값과 무게가 정확히 같은 i번째 물건이 Ki개 있다.
예를 들어 N = 3종류의 물건이 있다: 고기, 우유, 빵. 그중 고기는 1팩, 우유는 3병, 빵은 4개가 있다 (마지막 샘플 테스트 케이스를 참고하라).
장바구니에 담긴 물건들의 총 가치를 최대로 하려면 주부는 어떤 물건을 담아야 하는가?
입력
프로그램은 표준 입력에서 읽는다.
입력의 첫째 줄에는 두 양의 정수 S와 N이 주어진다.
다음 N개 줄에는 각각 세 정수가 주어지며, i번째 줄에는 i번째 물건의 가치 Vi(SGD), 무게 Wi(킬로그램), 개수 Ki가 주어진다.
출력
프로그램은 표준 출력에 출력한다.
주부가 총 무게가 S킬로그램을 넘지 않게 담을 수 있는 물건들의 최대 총 가치(SGD)를 정수 하나로 출력한다.
제한
- 1 ≤ S ≤ 2000
- 1 ≤ Vi ≤ 1000000
- 1 ≤ Wi ≤ S
- 1 ≤ N ≤ 100000
- 1 ≤ Ki ≤ 109