题目描述

英勇的厄崔迪小队正在执行任务。他们的任务是从厄拉科斯星球的不同的地区搜集尽可能多的香料，以对抗哈克南家族。厄拉科斯星球有 $n$ 个地区，第 $i$ 个地区有 $a_i$ 单位香料，厄崔迪小队使用一种叫做沙虫的交通工具，骑乘沙虫从任何地区前往该地区都要花费 $b_i$ 单位香料。不幸的是，香料不是一种可再生资源，所以如果你第二次到访一个地区，你在那里将搜集不到新的香料。

厄崔迪小队在地区 $P$，所以他们可以立马搜集这个地区的香料，然后他们就可以去执行任务了。只要他们的香料足够，即完成骑乘后他们剩余的香料量是非负的，他们就可以以任意顺序访问地区。最后，他们可能会在任何地区选择停下来，甚至可能连地区 $P$ 都没离开过就停下来。他们的目标是使搜集到的香料量最大化，如果有很多种方法可以达到这个目标，他们还想使他们访问过的不同地区的个数最大化，你能帮助他们对抗哈克南家族吗？

输入格式

第一行两个整数 $n,P$，以空格分隔，分别表示地区数量和起始地区编号。

接下来 $n$ 行每行两个整数 $a_i,b_i$。

输出格式

输出包含两行，每行一个正整数。

第一行表示当他们停下来时厄崔迪小队能搜集到的香料的最大值。

第二行表示在搜集到第一行所述香料量的前提下能访问到的最大的不同地区数。

样例

5 2
12 12
10 100
8 3
4 5
25 15

25
4

提示

一个最优的方案是，厄崔迪小队搜集完地区 $2$ 即起点的香料后从该地区出发，依次访问并搜集地区 $3,1,5$ 上的香料，途中花费分别为 $3,12,15$，从起点开始各个地区上完成搜集后剩余香料分别为 $10,15,15,25$。他们此时不应该选择去地区 $4$ 而是应该选择停下来以使结束时搜集到的香料量最大化。

数据范围

对于 $40\%$ 的测试数据，$1\le n\le10$；

对于 $100\%$ 的测试数据，$1\le P\le n\le10^5$，$a_i,b_i\le10^4$ 。