燃料搜集

题目描述

英勇的狐狸星小队正在执行任务。他们的任务是从莱拉星系的不同星球上搜集尽可能多的燃料。

莱拉星系中有 $n$ 个星球。第 $i$ 个星球上有 $a_i$ 单位燃料，但从任意其他星球飞往该星球需要消耗 $b_i$ 单位燃料。每个星球上的燃料只能收集一次，因此第二次到访同一星球时不会获得新的燃料。

狐狸星小队最初位于星球 $P$，因此可以立刻收集星球 $P$ 上的燃料，不需要支付前往星球 $P$ 的费用。

之后，只要当前燃料足够支付飞行费用，并且完成飞行后剩余燃料不少于 $0$，他们就可以按照任意顺序访问其他星球。到达一个尚未访问过的星球后，会立即收集该星球上的全部燃料。

他们可以在任意星球停止行动，也可以在收集完起点星球的燃料后立刻停止。

首先，他们希望停止时拥有的燃料数量最大。如果有多种方案能够获得相同的最大燃料，他们还希望访问过的不同星球数量尽可能多。

请你求出最大燃料量，以及在达到该燃料量的前提下最多能够访问的星球数量。

输入格式

第一行包含两个整数 $n,P$，分别表示星球数量和起始星球编号。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，分别表示星球 $i$ 上可以收集的燃料量，以及飞往星球 $i$ 所需的燃料量。

输出格式

输出两行，每行一个整数。

第一行表示停止时能够拥有的最大燃料量。

第二行表示在达到最大燃料量的前提下，最多能够访问的不同星球数量。

样例

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

25
4

样例说明

小队从星球 $2$ 出发，立刻得到 $10$ 单位燃料。

随后依次访问星球 $3,1,5$：

• 访问星球 $3$ 后，燃料变为 $10-3+8=15$；
• 访问星球 $1$ 后，燃料变为 $15-12+12=15$；
• 访问星球 $5$ 后，燃料变为 $15-15+25=25$。

此时不应访问星球 $4$，因为访问它会使燃料减少。

所以最大燃料量为 $25$，最多访问 $4$ 个不同星球。

数据范围

对于 $20\%$ 的测试数据：

对于全部测试数据：