수송기

먼 곳으로 물건을 배달해야 하는 수송기가 있습니다. 모든 물건을 싣고 싶지만, 수송기의 적재 용량(무게 한도) $W$를 초과할 수는 없습니다. $n$개의 물건이 있고 각 물건의 무게는 $w_1, w_2, \dots, w_n$, 가치는 $v_1, v_2, \dots, v_n$으로 주어집니다. 용량 $W$를 넘기지 않으면서 실을 수 있는 물건들의 부분집합 중에서 가치의 합이 최대가 되는 값을 구하세요.

첫 번째 줄에 문제 세트의 개수를 나타내는 양의 정수가 주어집니다. 각 문제 세트의 첫 번째 줄에는 두 양의 정수 $n$과 $W$가 주어지며, $n$은 물건의 개수, $W$는 수송기의 용량입니다. 이어지는 $n$개의 줄에는 각각 두 정수 $w$와 $v$가 주어지며, $w$는 물건의 무게, $v$는 물건의 가치입니다. 모든 무게와 가치는 양의 정수이고, 한 문제 세트의 물건 개수는 20개를 넘지 않습니다.

각 문제 세트마다, 용량 $W$를 초과하지 않고 수송기가 실을 수 있는 가장 가치 있는 부분집합의 가치 합을 한 줄에 하나씩 출력합니다.