어느 날, 골드는 보안이 허술한 보석상에 침입했습니다. 보석상에는 총 N 종류의 보석들이 진열되어 있습니다.

각 보석은 저마다의 무게 w_i와 가치 v_i를 가지고 있습니다.

보석상에는 각 종류의 보석이 무한히 많이 쌓여 있어서, 골드는 가방이 버틸 수만 있다면 같은 종류의 보석을 몇 개든 원하는 만큼 가방에 담을 수 있습니다.

골드가 가져간 배낭은 최대 W만큼의 무게를 버틸 수 있습니다.

골드가 가방에 담은 보석들의 총 무게가 W를 넘지 않으면서, 가방에 담긴 보석들의 총 가치의 합을 최대화하는 프로그램을 작성하시오.

입력

첫째 줄에 보석의 종류 N과 배낭이 버틸 수 있는 최대 무게 W가 공백을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 보석의 무게 w_i와 가치 v_i가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 골드가 가방에 담을 수 있는 보석의 최대 가치 합을 출력한다.

제한 사항

• 1 ≤ N ≤ 1,000

• 1 ≤ W ≤ 10,000

• 1 ≤ w_i ≤ W

• 1 ≤ v_i ≤ 1,000,000

First line \(N\) and \(W\); then \(N\) lines each with \(w_i\) and \(v_i\) (\(1 \le N \le 1000\), \(1 \le W \le 10000\), \(1 \le w_i \le W\), \(1 \le v_i \le 10^6\)).

Print the maximum achievable total value.

riseoj 작성

출처 Online Judge > GoldOJ