use crate::lib::stdio::*; fn main() { scan!(n: usize, mut ws: [(u64, u64); n]); // (w1, s1) の下に (w2, s2) があり、w1 + s1 >= w2 + s2 であるとき、 // s2 - w1 <= s2, s2 - w1 <= s1 - w2 より、 // これら 2 つの積み木を swap しても min(s1, s2 - w1) は減少しない。 ws.sort_unstable_by_key(|&(w, s)| w + s); // dp[X]: 条件を満たす X 個の積み木の重みの和の最小値 let mut dp = vec![u64::MAX; n + 1]; dp[0] = 0; for &(w, s) in &ws { for i in (0..n).rev() { if dp[i] <= s { dp[i + 1] = dp[i + 1].min(dp[i] + w); } } } for i in (0..=n).rev() { if dp[i] != u64::MAX { prtln!(i); return; } } } pub mod lib { pub mod stdio { pub use crate::prtln; pub use crate::scan; use std::io::{stdout, BufWriter, StdoutLock}; pub fn stdout_buf() -> BufWriter> { let out = Box::leak(Box::new(stdout())); BufWriter::new(out.lock()) } #[macro_export] macro_rules! prtln { (@ $dst:expr, iter=$expr:expr) => { $crate::prtln!(@ $dst, iter=$expr, sep=" "); }; (@ $dst:expr, iter=$expr:expr, sep=$sep:expr) => { { let mut iter = $expr.into_iter(); if let Some(expr) = iter.next() { std::write!($dst, "{}", expr).unwrap(); for expr in iter { std::write!($dst, "{}{}", $sep, expr).unwrap(); } } $crate::prtln!(@ $dst, ""); } }; (@ $dst:expr, $expr:expr, no eol) => { std::write!($dst, "{}", $expr).unwrap(); }; (@ $dst:expr, $expr:expr) => { std::writeln!($dst, "{}", $expr).unwrap(); }; (@ $dst:expr, $expr:expr, $($exprs:expr),*) => { { std::write!($dst, "{} ", $expr).unwrap(); $crate::prtln!(@ $dst, $($exprs),*); } }; (new $var:ident $(,)?) => { let mut $var = stdout_buf(); }; (new $var:ident, $($t:tt)*) => { $crate::prtln!(new $var); $crate::prtln!(to $var, $($t)*); }; (to $var:ident, $($t:tt)*) => { { use std::io::Write; $crate::prtln!(@ $var, $($t)*); } }; ($($t:tt)*) => { { $crate::prtln!(new __prtln, $($t)*); std::mem::drop(__prtln); } }; } #[macro_export] macro_rules! scan { (@ $iter:expr $(,)?) => {}; (@ $iter:expr, mut $var:ident : $t:tt $($r:tt)*) => { #[allow(non_snake_case)] let mut $var = $crate::scan_value!($iter, $t); $crate::scan!(@ $iter $($r)*) }; (@ $iter:expr, $var:ident : $t:tt $($r:tt)*) => { #[allow(non_snake_case)] let $var = $crate::scan_value!($iter, $t); $crate::scan!(@ $iter $($r)*) }; (@ $iter:expr, $pat:pat in $t:tt $($r:tt)*) => { let $pat = $crate::scan_value!($iter, $t); $crate::scan!(@ $iter $($r)*) }; (from $s:expr, $($r:tt)*) => { $crate::scan!(@ $s, $($r)*); }; (new $var:ident, $($r:tt)*) => { let mut __input = String::new(); std::io::Read::read_to_string(&mut std::io::stdin(), &mut __input).unwrap(); let $var = &mut __input.split_ascii_whitespace(); $crate::scan!(@ $var, $($r)*); }; ($($r:tt)*) => { $crate::scan!(new __scan, $($r)*); }; } #[macro_export] macro_rules! scan_value { ($iter:expr, ( $($t:tt),* )) => { ( $($crate::scan_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| $crate::scan_value!($iter, $t)).collect::>() }; ($iter:expr, bytes) => { $iter.next().unwrap().as_bytes() }; ($iter:expr, usize1) => { $crate::scan_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().unwrap() }; } } // mod stdio } // mod lib