题目描述

小卢卡斯在 卢卡斯OJ 上刷题。

卢卡斯OJ 上的每道题都有对应的积分。并且我们已知小卢卡斯刷每道题所需要花费的时间。

卢卡斯OJ 上目前一共有 $n$ 道题，小卢卡斯刷第 $i(1 \le i \le n)$ 道题需要花费 $c_i$ 分钟的时间可以 AC，AC 第 $i$ 道题能够增加的积分为 $w_i$。

已知：小卢卡斯给自己安排了 $V$ 分钟时间刷题，同时他希望他 AC 的题目能够获得的总分最大？

求：

1. 小卢卡斯刷题能够获得的最大积分；
2. 小卢卡斯获得最大积分对应的不同方案数（由于方案数可能很大，所以需要对 $10007$ 取模）。

说明：

• 小卢卡斯刷题的时间不一定要等于 $V$ 分钟，但不能大于 $V$ 分钟；
• 每道题只能刷一次，多刷没有积分；
• 刷题的间隔时间视为 $0$；
• 如果刷题的顺序不同，但是刷的题一样，视为同一种方案。

输入格式

第一行，两个整数 $n$ 和 $V$，以空格分隔。

接下来 $n$ 行，每行包含两个整数 $c_i$ 和 $w_i$，分别表示刷第 $i$ 道题的时间，以及能够获得的积分。

输出格式

输出共两行。

第一行，一个整数，表示小卢卡斯刷题能够获得的最大积分。

第二行，一个整数，表示小卢卡斯获得最大积分对应的不同方案数。

样例

3 6
2 3
5 7
3 5

8
1

5 10
2 2
4 4
5 5
7 7
9 9

9
3

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n, V \le 10$，$c_i \le V$，$w_i \le 10$
• 对于 $40\%$ 的数据，$n, V \le 100$，$c_i \le V$，$w_i \le 100$
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le V \le 10^4$，$1 \le c_i \le V$，$1 \le w_i \le 10^6$