当前没有测试数据。

题目描述

一辆勘测车将依次经过编号为 $1,2,\dots,n$ 的站点。站点的先后顺序由路线固定，勘测车不能改变顺序，也不能返回已经经过的站点。

勘测车的能量始终是非负整数。它以 $x$ 单位能量出发，其中 $x$ 由你决定。经过站点 $i$ 时，只能作出以下两种选择之一：

• 跳过该站点，能量不变；
• 完成该站点的勘测。只有当前能量不少于 $a_i$ 时才能这样做。勘测会消耗 $a_i$ 单位能量，随后立即从该站点获得 $b_i$ 单位补给。因此，若勘测前能量为 $e$，勘测后能量变为 $e-a_i+b_i$。

只有完成勘测才能获得该站点的补给。所有选择都必须在站点被经过时作出。

求最小的初始能量 $x$，使得存在一种方案完成至少 $k$ 个站点的勘测。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，描述站点 $i$。

输出格式

输出一个非负整数，表示满足要求的最小初始能量。

样例

4 2
6 0
5 8
9 0
12 0

6

样例解释 以 $6$ 单位能量出发，跳过站点 $1$，在站点 $2$ 完成勘测后能量变为 $6-5+8=9$，随后可以完成站点 $3$ 的勘测。因此能完成两个站点。 若初始能量不超过 $5$，站点 $1$ 无法完成；即使在能量为 $5$ 时完成站点 $2$，之后也只有 $8$ 单位能量，无法完成站点 $3$ 或站点 $4$。所以初始能量小于 $6$ 时至多完成一个站点。

数据规模与约定

• $1 \le k \le n \le 2\times 10^5$；
• $n\times k \le 2\times 10^7$；
• $1 \le a_i \le 10^9,\ 0 \le b_i \le 10^9$；

每个子任务是独立测试组，通过该组即可获得对应分值；各组分值相加，总分为 $100$ 分。

原题链接

原题链接