A171745.Yuilice 的分批冲印

Yuilice 要按顺序冲印 $n$ 张照片。第 $i$ 张照片的打印时间为 $t_i$，准备参数为 $s_i$。

她需要把这些照片分成至多 $k$ 个非空批次。每个批次必须是原序列中连续的一段，每张照片恰好属于一个批次，不能改变照片顺序。

一个批次的耗时等于其中所有照片的打印时间之和，再加上这些照片的准备参数的最大值。

请你求出：所有批次中最大耗时的最小可能值。

第一行包含两个整数 $n,k$，分别表示照片数量和允许划分的非空批次数量上限。

接下来 $n$ 行，第 $i$ 行包含两个整数 $t_i,s_i$，分别表示第 $i$ 张照片的打印时间和准备参数。

输出一个整数，表示所有批次中最大耗时的最小可能值。

样例解释

样例 $1$：分为第 $1$、$2$ 张和第 $3$、$4$ 张两批，耗时分别为 $2+3+4=9$ 和 $1+4+2=7$，最大值为 $9$。若上限为 $8$，前两张无法同批，后三张也无法同批，因此至少需要三批，超过限制。

样例 $2$：每张照片单独成批，耗时分别为 $9,1,6$，答案为 $9$。第一张照片所在批次的耗时不会小于 $9$。

数据范围

对于所有测试数据，满足 $1\le k\le n\le2\times10^5$，$1\le t_i\le10^9$，$0\le s_i\le10^9$。

测试点	分值	额外限制
1–2	10	$k=1$ 或 $k=n$
3–6	20	$n\le16$
7–20	70	无额外限制