解题思路

设营业时间为 $p$，只有满足 $b_i \le p$ 的顾客才真正需要被考虑。

因为当 $b_i > p$ 时，餐堂在该顾客截止时间之前就已经关门了，这位顾客会直接取消就餐，不会产生不开心。

于是对于一个固定的 $p$，问题变成：

• 从所有满足 $b_i \le p$ 的顾客中

题目内容

你开了一家食堂。新的一天的营业从第 $0$ 时刻开始，这一天食堂将迎来 $n$ 个顾客，其中第 $i$ 个顾客的食物需要花费 $a_i$ 个时间单位制作，等餐截止时间为 $b_i$ 。若$b_i$时刻末顾客仍未取得他的食物，则顾客会不开心。

你可以指定你的食堂的营业时间 $p$ ，这意味着 $p$ 时刻末之后你的食堂会关门。当顾客的等餐截止时间大于营业时间时，他会取消本次就餐，你不需要再制作该顾客的食物，他也不会因为等餐截止时间前未取得食物而不开心

定义 $f(p)$ 表示营业时间为 $p$ 时，最少有多少顾客不开心。请你计算

输入描述

输入第一行有一个整数 $n(1≤n≤10^5)$，表示顾客的数量。

接下来 $n$ 行中第 $i$ 行有两个整数 $a_i$ 和 $b_i(1≤a_i,b_i≤10^9)$，分别表示第 $i$ 个顾客的食物的制作时间和顾客的等餐截止时间。

输出描述

输出一个整数，表示 $\sum_{i=1}^{\max\limits (b_j)} f(i)$ 的结果。

样例1

输入

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$);

由上述$\sum ^{max(b_j)}_{i=1}f(i)=\sum ^8_{i=1}f(i)=f(1)+f(2)+...+f(8)=5$

答案为 $5$