M. 潇潇日暮时,掠水鸳鸯散。
题号:NC232163
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

嘘嘘非常爱玩炉石,尤其是对挨打的防战情有独钟。而防战的精髓就是“叠甲,过!”。

现在嘘嘘有n颗法力水晶,m张手牌(请注意此题规则和现实情况可能不一样,以题目为准)。
每张牌有两个值:a_ib_i。表示打出第i张牌,你的法力水晶就会减少a_i颗,并获得b_i点护甲值。
嘘嘘只是个摊煎饼的,不懂防战。所以他请你帮忙算算他最多能获得多少护甲值。

输入描述:

第一行两个数字,表示法力水晶数量和手牌的数量。
接下来m行,每行包括两个数,a_ib_i,分别表示第i张手牌的花费的法力水晶颗数和能获得的护甲值。

输出描述:

输出嘘嘘能获得的最大护甲值。
示例1

输入

复制
9 3
5 3
3 6
4 7

输出

复制
13

说明

嘘嘘选择出第二张牌,和第三张牌,这样的选择会获得最大的护甲值13。