Migrated from Lutece 1348 柱爷与咸鱼神功

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

某日，喵哈哈村，柱爷在自己房间内，面对魔镜

"魔镜啊，魔镜，什么才是这个世界上最强大的武功？"

霎时，一道惊雷落下，柱爷的面前竟然浮现出了一本古老的黑色书籍，而书的名字竟然是“咸鱼神功”!

翻开一看，书的第一页赫然写着：”练至大成可变身咸鱼王，掌控雷电！“

看到这句话，柱爷当即决定修炼咸鱼神功！

既然是神功，也不是那么好练的，因此柱爷决定好好的规划一下自己的修炼过程！

柱爷有$N$点心情值，而咸鱼神功则有$M$个招式，对于每个招式，柱爷必须要消耗$T_{i}$点心情值才能掌握，同时柱爷会获得$V_{i}$的修炼值

那么，柱爷能够获得的最大修炼值是多少呢？

Input

第一行两个整数$N$,$M$，分别表示柱爷的心情点数和咸鱼神功的招式数量

接下来$M$行，每行$2$个整数，$T_{i}，V_{i}$，分别表示学习该招式的消耗和能获得的修炼值

数据保证:

• $1 \leq N,M \leq 5000$

• $1 \leq T_{i},V_{i} \leq 10000$

Output

输出仅一行，表示柱爷能获得的最大修炼值

Samples

5 4
2 5
2 3
3 9
4 4

14

Resources

2016 UESTC Training for Dynamic Programming