use std::io::{self,Read}; fn main(){ let inf = 100_000; let mut buf = String::new(); io::stdin().read_to_string(&mut buf).unwrap(); let mut lines = buf.lines(); let n: usize = lines.next().unwrap().parse().unwrap(); let s: usize = 1 << n; let book:Vec<(i32,i32)> = lines.by_ref().take(n).map(|line| { let v:Vec = line.split_whitespace().map(|x| x.parse().unwrap()).collect(); (v[0], v[1]) }).collect(); let mut dp:Vec> = (0..n).map(|_i| vec![inf; s] ).collect(); for i in 0 .. n { dp[i][1 << i] = 0; } for state in 1 .. s { let (used, unused): (Vec, Vec) = (0 .. n).partition(|x| state & (1_usize << x) > 0 ); for &j in unused.iter() { dp[j][ state | (1_usize << j)] = used.iter() .fold(inf,|m, &i| std::cmp::min(m, std::cmp::max(dp[i][state], book[i].1 - book[i].0 + book[j].0))); } } println!("{}", (0..n).map(|i| dp[i][s - 1] ).min().unwrap()); }