题目内容

职工食堂新开了自选套餐。窗口今天一共摆出 $k$ 道菜，编号为 $j$ 的菜标价 $c_j$ 元，归属类别 $g_j$。类别分成四种：$1$ 代表主食，$2$ 代表荤菜，$3$ 代表素菜，$4$ 代表汤。

从这 $k$ 道菜里挑出一部分（同一道菜至多挑一回）就构成一份套餐，套餐要同时符合下面两条：

• 四种类别里，每种类别都挑到至少一道；
• 挑出的菜品标价相加，结果不得大于预算 $M$。

若两份套餐挑选的菜品集合有差别，就记为两份不同的套餐，哪怕二者总价一样。

请求出满足要求的套餐一共有几份，并找出这些套餐里最高的总价。

输入描述

首行给出两个整数 $k$ 与 $M$。

随后 $k$ 行，每行两个整数 $c_j$ 和 $g_j$，分别是第 $j$ 道菜的标价和类别。

输出描述

在一行内输出两个整数：符合要求的套餐份数，以及这些套餐里的最高总价。

倘若一份符合要求的套餐都没有，就输出 0 -1。

数据范围：

• $1\le k\le 15$
• $1\le M\le 10^6$
• $1\le c_j\le 10^5$
• $g_j\in\{1,2,3,4\}$

样例1

输入

6 24
5 1
8 2
6 2
4 3
7 3
3 4

输出

4 23

说明

把这 $6$ 道菜按顺序叫作 $A\sim F$。主食仅有 $A$，汤仅有 $F$，这两道必须挑上，花去 $5+3=8$ 元，预算还剩 $16$ 元。

荤菜能挑 $\{B\}$、$\{C\}$ 或 $\{B,C\}$；素菜能挑 $\{D\}$、$\{E\}$ 或 $\{D,E\}$。把荤素两部分的花费逐个和 $16$ 比较：

• $\{B,D\}$：$12$，可行，总价 $20$；
• $\{B,E\}$：$15$，可行，总价 $23$；
• $\{B,D,E\}$：$19$，超支；
• $\{C,D\}$：$10$，可行，总价 $18$；
• $\{C,E\}$：$13$，可行，总价 $21$；
• $\{C,D,E\}$：$17$，超支；
• $\{B,C\}$ 单这两道就要 $14$ 元，再配哪种素菜（最便宜也要 $4$ 元）都会超支。

可行的套餐一共 $4$ 份，最高总价是 $23$。

样例2

输入

4 10
3 1
4 2
2 3
2 4

输出

0 -1

说明

四个类别都只有一道菜，想凑齐四类只能全挑，总价 $3+4+2+2=11$，比预算 $10$ 多，所以一份可行的套餐也没有。