//! # Bundled libraries //! //! - `procon_reader 0.1.0 (git+https://github.com/ia7ck/rust-competitive-programming#59eb5cd766b43a170294fe6e7a7026645fc306e3)` licensed under **missing** as `crate::procon_reader` use procon_reader::ProconReader; fn main() { let stdin = std::io::stdin(); let mut rd = ProconReader::new(stdin.lock()); let n: usize = rd.get(); let ws: Vec<(u64, u64)> = (0..n) .map(|_| { let w: u64 = rd.get(); let s: u64 = rd.get(); (w, s) }) .collect(); let mut ws = ws; ws.sort_by_key(|(w, s)| w + s); let inf = std::u64::MAX / 2; let mut dp = vec![vec![inf; n + 1]; n + 1]; dp[0][0] = 0; for (i, &(w, s)) in ws.iter().enumerate() { for j in 1..=n { dp[i + 1][j] = dp[i + 1][j].min(dp[i][j]); if s >= dp[i][j - 1] { dp[i + 1][j] = dp[i + 1][j].min(dp[i][j - 1] + w); } } } let ans = dp[n].iter().rposition(|&x| x != inf).unwrap(); println!("{}", ans); } // The following code was expanded by `cargo-equip`. #[cfg_attr(any(),rustfmt::skip)]#[allow(unused)]pub mod procon_reader{pub struct ProconReader{r:R,l:String,i:usize,}implProconReader{pub fn new(reader:R)->Self{Self{r:reader,l:String::new(),i:0,}}pub fn get(&mut self)->T where T:std::str::FromStr,::Err:std::fmt::Debug,{self.skip_blanks();assert!(self.i{self.i+=j;break;}None=>{let mut buf=String::new();let num_bytes=self.r.read_line(&mut buf).unwrap_or_else(|_|panic!("invalid UTF-8"));assert!(num_bytes>0,"reached EOF :(");self.l=buf.trim_end_matches('\n').trim_end_matches('\r').to_string();self.i=0;}}}}pub fn get_vec(&mut self,n:usize)->Vecwhere T:std::str::FromStr,::Err:std::fmt::Debug,{(0..n).map(|_|self.get()).collect()}pub fn get_chars(&mut self)->Vec{self.get::().chars().collect()}}}