描述

有一列N个平台，每个平台有高度H，平台上有金币V
网友可以从任一个平台出发向左跳
网友可以跳到他左侧任一个高度小于他所在平台的平台上
或者跳到地上，结束跳跃
只要网友经过，平台上的金币就会被网友收集
网友想知道他收集至少M个金币的方案数
两个方案不同指方案所经过的平台集合不同

输入

第一行两个正整数N,M
接下来N行每行两个正整数Hi,Vi
其中第i行为从左到右第i个平台的信息

输出

一行一个整数
为方案数

样例

输入

3 6
2 5
3 6
4 7

输出

6

范围

50% N<=20
100% N<=40 Hi,Vi<=\(4\ast 10^7\) M<=\(\sum Vi\)

限制

1s
128M

来源