设营业时间为 p,只有满足 bi≤p 的顾客才真正需要被考虑。
因为当 bi>p 时,餐堂在该顾客截止时间之前就已经关门了,这位顾客会直接取消就餐,不会产生不开心。
于是对于一个固定的 p,问题变成:
你开了一家食堂。新的一天的营业从第 0 时刻开始,这一天食堂将迎来 n 个顾客,其中第 i 个顾客的食物需要花费 ai 个时间单位制作,等餐截止时间为 bi 。若bi时刻末顾客仍未取得他的食物,则顾客会不开心。
你可以指定你的食堂的营业时间 p ,这意味着 p 时刻末之后你的食堂会关门。当顾客的等餐截止时间大于营业时间时,他会取消本次就餐,你不需要再制作该顾客的食物,他也不会因为等餐截止时间前未取得食物而不开心
定义 f(p) 表示营业时间为 p 时,最少有多少顾客不开心。请你计算
输入第一行有一个整数 n(1≤n≤105),表示顾客的数量。
接下来 n 行中第 i 行有两个整数 ai 和 bi(1≤ai,bi≤109),分别表示第 i 个顾客的食物的制作时间和顾客的等餐截止时间。
输出一个整数,表示 ∑i=1max(bj)f(i) 的结果。
输入
5
4 7
1 2
3 4
2 8
2 5
输出
5
说明
营业时间 p=1 时,没有顾客就餐,f(1)=0;
p=2 时,编号为 2 的顾客就餐,从第一个时刻开始制作 2 号顾客的食物,第 1 个时刻末食物制作完成,没有超过 2 号顾客的等餐截止时间,因此 f(2)=0;
p=3 时,情况同上, f(3)=0;
p=4 时,先制作 2 号顾客的食物,然后立刻制作 3 号顾客的食物,两人均能在等餐截止时间前取得食物,因此 f(4)=0;
p=5 时,2 号、3 号和 5 号顾客中至少有一位的食物无法在等餐截止时间前制作完成,因此 f(5)=1;
p=6 时,情况同上,f(6)=1;
p=7 时,按顺序依次制作 2号、5 号和 1号顾客的食物,仅有 3号顾客的食物无法在等餐截止时间前制作完成,f(7)=1;
p=8 时,按顺序依次制作 2号、5 号和 4 号顾客的食物,2 号和 3 号顾客的食物无法在等餐截止时间前制作完成,f(8)=2 (也可以按顺序制作 2号、5号和1号顾客的食物,答案依然是 2);
由上述∑i=1max(bj)f(i)=∑i=18f(i)=f(1)+f(2)+...+f(8)=5
答案为 5