배낭 문제

아래 배낭 문제를 푸시오. 무게는 무작위 필터로 평활화되어 있습니다.

To fit the best stuff in a sack with limits on what you can pack recursion will do if memoized too but DP puts less on the stack.

$n$개의 원소 $(w\_1, v\_1), \dots, (w\_n, v\_n)$과 용량 $W$가 주어진다. 다음 값을 구하라.

$\max\_{\substack{S \subseteq \[n]\\\\\sum\_{i\in S} w\_i \leq W}} \sum\_{i \in S} v\_i\text{.}$

여기서 $\[n]$은 1부터 $n$까지의 정수 리스트이다.

$0 \leq n \leq 500$, $0 \leq w\_i \leq W \leq 10^{17}$, $0 \leq v\_i \leq 10^{16}$을 만족한다고 보장한다. 또한 무게 $w\_i$는 아래 설명대로 평활화되어 있다고 보장한다.

먼저 위 제약을 만족하는 인스턴스를 만든다. 그다음 무작위 필터를 적용한다. $B$를 원소 중 가장 큰 무게라고 하자. 각 무게는 다음과 같이 갱신된다.

$w\_i \leftarrow \min (w\_i + \mbox{rand}(\lfloor .05 B \rfloor), W)$

여기서 $\mbox{rand}(A)$는 $[0, A-1]$ 범위의 균등 난수 정수를 돌려준다. 이 필터는 $w\_i$에만 적용되며 $W$나 다른 값은 바꾸지 않는다.

첫 줄에 두 정수 $n$과 $W$가 공백으로 구분되어 주어진다. 이어지는 $n$개의 줄에는 각각 두 정수 $w\_i$와 $v\_i$가 공백으로 구분되어 주어진다. 무게는 위에서 설명한 방식으로 만들어진다. 먼저 제약을 만족하는 인스턴스를 고르고, 그 뒤에 평활화를 적용한다. 프로그램이 입력으로 받는 값은 평활화를 거친 결과이다.

주어진 배낭 문제의 값을 한 줄에 출력하라.