题目描述

你决定练习，练习意味着在 AtCoder 中解决大量问题。

练习需要几天时间。每天的练习分为以下步骤。

设 $M$ 是当天要解决的问题数。每个问题都有一个称为难度的值，它是一对非负整数（$A$，$B$）。

首先，以任何顺序重新排列 $M$ 个问题。然后，按该顺序逐个解决问题。

您有一个称为疲劳的值。疲劳在开始一天时为 0，当解决难度为（$A$，$B$）的问题时，它从 $x$ 变为 $Ax + B$。

解决所有 $M$ 个问题的疲劳在解决当天的能量消耗中。

在 AtCoder 中有一个 $N$ 个问题的序列，按顺序称为问题 1、问题 2，…，问题 $N$。问题i的难度为（$A_i$，$B_i$）。

您决定通过练习解决所有 $N$ 个问题。

练习分为以下步骤。下面，让 $[L,R]$ 表示以下问题序列：问题 $L$，问题 $L + 1$，$\cdots$，问题 $R$。

自由选择 1 到 $N$（含）之间的整数 $K$。练习将持续 $K$ 天。

将 $N$ 个问题的顺序连续子序列分成 $K$ 个非空连续子序列，并让 $S_i$ 为第 $i$ 个序列。

形式上，选择一个严格递增的非负整数序列 $x_0,x_1,\cdots,x_K$，使得 $1 = x_0$ 且 $x_K = N + 1$，并让 $S_i = [xi-1，xi-1]$ 对于 $1≤i≤K$ 中的所有问题。

然后，对于 $i = 1,2,\cdots,K$，解决第 $i$ 天练习中的所有问题 $S_i$。

你决定练习，使得整个练习中消耗的总能量最多为 $X$。

让 $D$ 是 $K$ 的最小可能值，即天数，以进行这样的练习。（在此约束下，$D$ 始终存在）

还让 $M$ 是在 $K = D$ 的情况下消耗的最小总能量。

找到 $D$ 和 $M$。

输入

输入格式为：

$N X$

$A_1 B_1$

$A_2 B_2$

⋮

$A_N B_N$

输出

输出 $D$ 和 $M$，用空格分隔。