灰灰的婚姻 / 【模板】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 范围内