2828 「CCC 2014 S2」燃料搜集

本题译自 CCC 2014 Stage2 Day2 T1「Where's That Fuel?」

英勇的狐狸星小队正在执行任务。他们的任务是从莱拉星系的不同的星球上搜集尽可能多的燃料。莱拉星系里有 $N$ 个星球，第 $i$ 个星球有 $A_i$ 单位燃料，但是从任何星球去那里都要花费 $B_i$ 单位燃料。不幸的是，燃料不是一种可再生资源，所以如果你第二次到访一个星球，你在那里将搜集不到新的燃料。

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

第一行两个整数 $N,P$，以空格分隔，分别表示星球数和起始星球编号。

接下来 $N$ 行每行两个整数 $A_i,B_i$。

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

第一行表示当他们停下来时狐狸星小队能搜集到的燃料的最大值。

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

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

对于 $20\%$ 的测试数据，$1\le N \le 10$；

对于 $100\%$ 的测试数据，$1\le P \le N \le 10^5,$ $1\le A_i,B_i\le 10^4$。