题目描述

你曾经梦想过你是电脑游戏中的主角吗？这个故事的主角，$\red{Branimir，}$现在正在做这个梦。

在$\red{Branimir}$的梦中，世界是由从左到右排列的$\red{N}$座摩天大楼组成的。对于第$\red{i}$座摩天大楼，我们知道摩天大楼的高度$\red{Hi}$和房顶金币的数量$\red{Gi}$。游戏从在任何摩天大楼上跳跃开始，由几步组成。在每一步中，$\red{Branimir}$都可以从他目前所在的摩天大楼向右跳$\red{}$(他也有可能跳过其中的几个$\red{}$)，到一个高度不低于现在的摩天大楼。

假如$\red{Branimir}$在一座摩天大楼，他可以拿这座大楼的金币。$\red{Branimir}$可以在任意步数之后结束游戏($\red{0}$步也可以$\red{}$)通往下一关，但必须要收集至少$\red{K}$个金币。

现在要求$\red{Branimir}$通往下一关的方案数。两个方案当做不同当且仅当$\red{Branimir}$在其中一次跳过其中一座摩天大楼而另一次没有。

输入格式

第一行输入一个正整数$\red{n，}$表示总的动物数。

接下来一行$\red{n}$个正整数，分别表示$\red{n}$只动物的种类，以顺时针的方向给出。$\red{0}$代表羊，$\red{1}$代表狼。

输出格式

第一行包含两个整数$\red{n,K}$

接下来$\red{n}$行，每行两个整数$\red{Hi}$和$\red{Gi }$

样例

输入样例1

2 9 2

0 14 6

2 1

6 3

7 2

5 6

输出样例1

1

输入样例2

2 7

4 6

3 5

输出样例2

0

输入样例3

4 15

5 5

5 12

6 10

2 1

输出样例3

4

提示

数据范围

对于$\red{40\%}$的数据，$\red{1<=n<=20}$

对于$\red{100\%}$的数据，$\red{1<=n<=40,1<=k<=4\times 10^{10},1<=Hi,Gi<=10^9}$

样例$\red{1}$解释

$\red{\{1,2,3\},\{1,4\}\{4\}}$三种方案