说明

辰辰是一位天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为了验证他的资质，他决定拜附近最有威望的医师为师。这位医师给他出了一个挑战：在一个充满草药的山洞中，每株草药采摘所需的时间和其自身价值各不相同。医师给定一段时间，在这段时间内，辰辰需要尽可能采集到总价值最大的草药。

你能否帮助辰辰完成这个任务呢？

输入格式

每组输入数据的第一行包含两个整数 T（1 <= T <= 1000）和 M（1 <= M <= 100），两者之间用空格分隔，T 表示总共可用于采药的时间，M 表示山洞里草药的数量。接下来的 M 行中，每行包括两个在 1 到 100 之间（含 1 和 100）的整数，分别表示采摘某株草药所需的时间和这株草药的价值。

• 数据规模：
  • 对于 30% 的数据，M <= 10；
  • 对于全部的数据，M <= 100。

输出格式

每组输出仅包含一行，该行是一个整数，表示在规定时间内可以采集到的最大草药总价值。

样例

70 3
71 100
69 1
1 2

3