草药大师
题号:NC235951
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有 n 种草药,收集第 i 种草药需要花费 t_i 的时间,能够带来 v_i 的价值,每种草药只能收集一次。为了成为草药大师,你需要一个人收集草药。请问在 S 的时间内,你最多能收集价值和多大的草药。


输入描述:

第一行输入两个整数  。

接下来 n 行,每行两个整数  ,分别表示收集每种草药需要花费的时间和收集草药带来的价值。

输出描述:

输出一行一个整数,表示在 S 的时间内,你最多能收集多少价值的草药。
示例1

输入

复制
3 70
71 100
69 1
1 2

输出

复制
3