문제 141
용량 이하 최대 무게
$N$개의 물건이 있고, 각 물건의 무게는 $W_1, W_2, \cdots, W_N$이다.
무게 합의 상한을 나타내는 정수 $T$가 주어진다. 각 물건을 최대 한 번 선택하여 무게의 합이 $T$ 이하가 되게 하려고 한다. 가능한 무게 합의 최댓값을 구해 보자.
입력
첫 번째 줄에 정수 $N$, $T$가 공백으로 구분되어 주어진다. $(0\le N\le200\,000; 0\le T\le2^{31}-1)$
두 번째 줄에 정수 $W_1, W_2, \cdots, W_N$이 공백으로 구분되어 주어진다. $(0\le W_i\le2\,000; N>0\Rightarrow N\max_{1\le i\le N}W_i\le4\cdot10^7)$ $N=0$이면 이 줄은 빈 줄이다.
출력
가능한 무게 합의 최댓값을 출력한다.
예제 입력 1
5 12 0 7 6 5 0
예제 출력 1
12