该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$N$个物品，每个物品价格范围为$minT_i,maxT_i$，你有$M$元钱，请问你可否能买到所有的$N$个物品并把$M$元钱恰好都花光。

如能，第一行输出1, 第二行分别输出购买每个物品的价格，如不能，输出2。

输入格式

第一行包含两个整数：$N,M$。

接下来 $N$ 行，每行两个数：$minT_i,maxT_i$，两个整数之间有一个空格，意义如题目描述。

输出格式

如能，第一行输出1, 第二行分别输出购买每个物品的价格，如不能，输出2。

输入输出样例 #1

输入 #1

1 48
5 7

输出 #1

2

输入输出样例 #2

输入 #2

2 5
0 1
3 5

输出 #2

1
1 4

说明/提示

【数据范围】

数据范围与提示

$1\le N\le30,0\le M\le240$

$0\le minT_i\le maxT_i\le10$