题目概述

• 命题人：Stardust D.L.
• 时间限制：1s
• 空间限制：524288KB
• 测试点数：20

题目描述

小笼包 叉烧包 奶黄芝麻豆沙包
大肉包 菜包 还有灌汤包
吃在人 命在天 亘古滔滔转眼间
唯席上 千年丰盛永不变
——千年食谱颂

---

一天，小乐对小洛说，隔壁的包子铺降价了，小洛很开心。于是她第二天就到了这家包子铺。包子铺有很多种包子，不同包子价钱wi（元每个）不一样，虽然对于小洛来说，包子都好吃，但是不同包子还是有不同的美味度qi的。因为小洛是个吃货，所以她一定要多吃。这天，她带了M元钱，她想买一些包子吃，但不想同一种吃多个（新鲜感很重要），请问她吃的包子美味度之和Q最大是多少？

输入

第一行 M N
第二行到第N+1行 wi qi

输出

Q

样例1

输入

70 3
71 100
69 1
1 2

输出

3

样例2

输入

200 8
79 83
58 14
86 54
11 79
28 72
62 52
15 48
68 62

输出

334

数据范围

\(2<=N<=35,1<=wi,qi<=10^9,W,Q<=10^{18}\)

数据分布

1-3 \(2<=N<=5,1<=wi,qi<=10^4\)
4-8 \(8<=N<=16,10^4<=wi,qi<=10^5\)
9-12 \(24<=N<=32,10^5<=wi,qi<=10^6\)
12-17 \(24<=N<=34,10^6<=wi,qi<=10^9\)
18-20 无特殊限制

闲聊

• 好好读题，小心被坑
• 多想正解
• 可以乱搞部分分

• 都是随机数据

• 包子真是贵啊，《论吃货是个土豪》
  ——From Stardust