Background

Special for beginners, ^_^

Description

学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能多得分。

现在要进行一次竞赛，总时间 $T$ 固定，有若干类型可选择的题目，每种类型题目可选入的数量不限，每种类型题目有一个 $s_i$（解答此题所得的分数）和 $t_i$（解答此题所需的时间），现要选择若干题目，使解这些题的总时间在 $T$ 以内的前提下，所得的总分最大。

输入包括竞赛的时间 $M\ (1\le M\le 10000)$ 和题目类型数目 $N\ (1\le N\le 10000)$。

后面的每一行将包括两个整数来描述一种"题型":

第一个整数说明解决这种题目能得的分数($1\le points\le 10000$)，第二整数说明解决这种题目所需的时间($1\le minutes\le 10000$)。

Format

Input

第 $1$ 行两个整数：竞赛的时间 $M$ 和题目类型数目 $N$。

第 $2\sim N+1$ 行两个整数：每种类型题目的分数和耗时。

Output

单独的一行，在给定固定时间里得到的最大的分数。

Samples

300 4
100 60
250 120
120 100
35 20

605

Limitation

1s, 1024KiB for each test case.

从第 2 种类型中选两题和第 4 种类型中选三题。