说明

小L被要求在20号之前必须出一道内卷题，但摆烂的TA不想内卷，甚至还想玩一把黄金矿工。更可气的是，躺平的TA不想自己思考，于是TA问你TA该钩起哪些物件最为合算。

关卡数据中，每个关卡有T秒的时间限制，一共有n个物件

输入

第一行输入该关卡总共时间T和总物件数量n
随后n行输入，每行两个数字vi，wi，分别表示第i个物品的价值和钩起花费的时间

($0\leq T,n,vi,wi\leq1000$)

输出

输出一种方案，该方案要求为字典序最小

示例

8 4
3 2
4 3
5 4
6 5

2 4

时间限制

1s, 1024KiB for each test case.