1603: 窈窕淑女
题目描述
“关关雎鸠，在河之洲。窈窕淑女，君子好逑。”――《诗经》
T博士的大儿子阿T（阿嚏？）最近遇到了一件麻烦事。
有n个MM同时邀请阿T在8月14日上午11:30拜访她们家，可那时阿T刚比赛完，所以不能先提前拜访几个，而他又不会分身术，所以他只得分别拜访。他共有T分钟的时间可以用于拜访MM。他还安排好了拜访的顺序，对于每个MM都可以选择拜访或不拜访。对于要拜访的MM必须按阿T安排好的顺序拜访。
对于每个MM都有如下数据：
不高兴系数x，为2到9的整数。
不高兴度X，若阿T迟到t分钟到她家，则X=x^t（x的t次方）；若阿T不拜访她家，则X=x^T。
拜访时间y（分钟），保证0<yi<=T，即阿T在她家停留的时间，若阿T在到了她家但停留时间不足y分钟，她的不高兴度就会变成正无穷大。
假设阿T从一个地方到另一个地方不用消耗时间，阿T希望在有限的T分钟里使所有MM的不高兴度之和最小。请告诉他这个最小值是多少。
输入
第一行是两个正整数n和T。
第1+i(1<=i<=n)有两个正整数xi和yi，分别是阿T安排的拜访顺序中第i个MM的不高兴系数和拜访时间。
输出
样例输入 复制
2 100
5 30
2 70
样例输出 复制
1073741825提示
【样例输入1】
2 100
5 30
2 70
【样例输出1】
1073741825 （两个MM都拜访，到第一个MM家时迟到了0分钟，到第二个MM家时迟到了30分钟，所以不高兴度之和为5^0+2^30）
【样例输入2】
2 30
5 16
2 16
【样例输出2】
1073741825 （只拜访第一个MM，到她家时迟到了0分钟，不高兴度之和为5^0+2^30；若只拜访第二个MM，则不高兴度之和为2^0+5^30，显然较大）
【数据范围】
对于20%的数据，满足1<=n<=10,1<=T<=9；
对于50%的数据，满足1<=n<=20,1<=T<=30；
对于100%的数据，满足1<=n<=20,1<=T<=180；