英雄般的 Star Fox 战队正在执行一项任务，从莱拉特星系的各个行星上收集尽可能多的燃料。星系中共有 $N$（$1 \le N \le 10^5$）个行星，其中第 $i$ 个行星含有 $A_i$ 个燃料电池。然而，从任何其他行星旅行到第 $i$ 个行星需要消耗 $B_i$ 个燃料电池（$1 \le A_i, B_i \le 10^4$）。不幸的是，燃料电池不是一种可持续资源，因此如果一个行星被第二次访问，将没有新的燃料可以收集。

Star Fox 战队从行星 $P$（$1 \le P \le N$）出发——因此，他们可以立即收集该行星上的燃料电池。然后，他们可以按任意顺序旅行到任意多个不同的行星，只要他们有足够的燃料来支付每次飞行的开销（即他们的燃料电池数量保持非负）。最后，他们可以选择在任何时候停止（甚至可能在离开行星 $P$ 之前），目标是最大化他们最终拥有的燃料电池数量。如果可以通过多种方式达到这一最大值，作为次要目标，他们希望最大化他们访问过的不同行星的数量。你能帮助我们的英雄吗？

输入格式

第一行包含两个整数：$N$（$1 \le N \le 10^5$）和 $P$（$1 \le P \le N$），中间用一个空格分隔，分别表示行星的数量和起始行星的编号。

接下来的 $N$ 行，每行包含 $A_i$ 和 $B_i$（$1 \le A_i, B_i \le 10^4$），中间用一个空格分隔。

输出格式

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

第一行包含 Star Fox 战队决定停止时所能拥有的最大燃料电池数量。

第二行包含在能够获得该最大燃料电池数量的前提下，Star Fox 战队所能访问的最大不同行星数量。

数据范围

对于占总分 20% 的测试用例，满足 $N \le 10$。

样例

输入样例 1

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

输出样例 1

25
4

说明

Star Fox 战队从行星 2 开始，首先收集 10 个燃料电池。接着，他们应该旅行到行星 3，消耗 3 个燃料电池，但随后将他们的燃料电池数量增加到 15。接下来，他们可以飞往行星 1，将燃料电池数量降低到 3，但随后立即恢复到 15。最后，他们拥有刚好足够的燃料到达行星 5，此时他们可以收集其燃料电池，最终拥有 25 个燃料电池。然后他们应该选择停止，而不去访问行星 4。