#P1252. 吃核桃的nana

吃核桃的nana

问题描述

核桃王国的nana女王肚子有点饿了,但是她身边只有很多核桃。设nana现在的饱腹值为 00,nana为了吃饱(吃饱的饱腹值为 nn ),她开始吃核桃了。已知有 mm 个核桃,众所周知核桃补脑,所以每个核桃都有它的饱腹值 xx 和补脑疗效 yy 。为了nana的身体健康,请从nana在空腹到吃饱的过程中,计算出nana吃核桃所能得到的最高的补脑疗效。

输入格式

第一行两个整数 nmn、m

以下 mm 行,每行有两个整数:xix_iyiy_i 分别表示第 ii 个核桃的饱腹值和疗效。

输出格式

输出一个整数表示最高补脑疗效。

50 3
5 2
45 3
1 3
6

样例解释

吃第二个和第三个核桃,可以疗效最大化,同时饱腹感之和不超过 50

测评数据规模

对于 100%100\% 的数据,0n,xi,yy100000 \le n,x_i,y_y \le 100000m100 \le m \le 10