Stealing books - MarisaOJ: Marisa Online Judge

Stealing books

Time limit: 1000 ms
Memory limit: 256 MB
Marisa has broken into the library of Scarlet Devil Mansion. There are $n$ books here, the $i^{th}$ book weighs $w_i$ and Marisa can read this book in $v_i$ days. Now she wants to "steal" some books, but their weight cannot exceed $S$. She also wants to read these books in as much time as possible. ### Input - The first line contains 2 integers $n, S$ - The next $n$ lines, each line contains 2 integers $w_i, v_i$. ### Output - Print the maximum reading time. ### Constraints - $1 \le n \le 40$. - $1 \le w_i, v_i, S \le 10^9$. ### Example Input: ``` 3 4 1 1 2 2 3 3 ``` Output: ``` 4 ```