这是一个16进制的世界，比如522的16进制是1314。

在5月22日那天，有人送给Bob一些月饼，每个月饼有饱食度和幸福度两个属性。

现在Bob有$n$个月饼，对于每个月饼$i$，饱食度为$v_i$，幸福度为$w_i$。

Bob现在有$m$饱食度，意味着他吃的月饼的饱食度之和不大于$m$。

但是由于Bob身处16进制的世界，他吃的月饼的幸福度之和必须是16的倍数。

请帮Bob算一下他最多吃的月饼的数量。

第一行输入两个整数$n,\ m$

接下来$n$行分别输入$v_i, \ w_i$表示第$i$个月饼的饱食度和幸福度。

输入数据保证$1 \leq n \cdot m \leq 10^5$, $ 1 \leq v_i \leq 10^5$, $1 \leq w_i \leq 10^9$。

一个整数，表示Bob最多能吃的月饼数量。