First, sort the friends according to their distances. Then we enumerate the friends. When we do not have enough money to go to the place of the current friend, we break the loop, spend the remaining money and stop.

• Time complexity is \(\mathcal{O}(N\log N)\).
• Space complexity is \(\mathcal{O}(1)\).

use proconio::input;

fn main() {
    input! {
        n: usize,
        mut k: usize,
        mut friends: [(usize, usize); n],
    }

    friends.sort();
    let mut now = 0;
    for (friend, money) in friends {
        if now + k < friend {
            break;
        }
        k -= friend - now;
        k += money;
        now = friend;
    }

    println!("{}", now + k);
}