Stealing books - MarisaOJ: Marisa Online Judge

Marisa has broken into the library of Scarlet Devil Mansion. There are

n

$n$ books here, the

i^{t h}

$i^{th}$ book weighs

w_{i}

$w_i$ and Marisa can read this book in

v_{i}

$v_i$ days. Now she wants to "steal" some books, but their weight cannot exceed

S

$S$ . She also wants to read these books in as much time as possible. ### Input - The first line contains 2 integers

n, S

$n, S$ - The next

n

$n$ lines, each line contains 2 integers

w_{i}, v_{i}

$w_i, v_i$ . ### Output - Print the maximum reading time. ### Constraints -

1 \leq n \leq 40

$1 \le n \le 40$ . -

1 \leq w_{i}, v_{i}, S \leq 10^{9}

$1 \le w_i, v_i, S \le 10^9$ . ### Example Input:

34112233

$3 4 1 1 2 2 3 3$

Output:

4

$4$

Topic

Meet in the middle

Rating

1000

Solution (0)

Solution