灰灰的婚姻 / 【模板】01背包DP

灰灰的婚姻 / 【模板】01背包DP

题目描述

灰灰今天心情很好,在MPT管理群里有\(M\)个漂亮的女孩。灰灰很年轻,比较花心,所以灰灰非常喜欢他们。
但是灰灰不是活在古代,他不能一次娶所有女孩纸啊,因此灰灰每次只能挑选一个女孩纸结婚。与每个女孩子结婚,灰灰都能获得一些快乐。与第\(i\)的女孩纸结婚能获得\(a_i\)个快乐值。
因为灰灰比较花心,他与一个女孩纸结婚后过几年就会离婚然后追求其他女孩子,而被抛弃的女孩纸就会退群,灰灰无法再与他相处。
已知第\(i\)个女孩纸会与灰灰一起生活\(b_i\)年,给定灰灰的大限\(N\),因为灰灰不会算法,所以请你帮他算一下如何结婚才能获得最多的快乐值。

输入格式

第一行两个整数,\(N\)与\(M\),分别表示灰灰的大限与女孩纸个数
接下来\(M\)行,每行两个整数\(a\)与\(b\),分别表示与这个女孩结婚能获得的快乐值和相处时长

输出格式

一个整数,表示能获得的最大快乐值

样例

输入

15 5
1 5
3 6
5 8
2 5
3 6

输出

8

数据范围

对于\(100\%\)的数据,\(M \leqslant 100\)

保证 \(\sum_{i = 1}^{n}{a_i}\) 在 int 范围内

信息

ID
1002
难度
3
分类
动态规划 | 背包 点击显示
标签
递交数
47
已通过
3
通过率
6%
上传者