Background

kunkka占领了高地，人类气急败坏，擂起了鼓，战斗开始了。不过，kunkka找来了会使用魔法的博博，让他用魔法来战胜愚蠢的人类。

Description

博博有k点魔法能量，他还有m个招数，每个招数都要花费$v[i]$个魔法能量使用，但这会对人类造成$w[i]$点打击。招数可无限次使用，但使用前魔法能量要足够。请问，博博最多能对人类造成多少点打击呢？

Format

Input

第一行两个整数，k，m。后面m行，每行两个整数，表示$v[i]$和$w[i]$。

Output

一个整数，表示博博最多能对人类造成多少点打击。

Samples

16 4
2 8
4 16
8 32
16 65

65

Limitation

1s, 1024KiB for each test case. $1≤k≤1000，1 \le m \le 10000, v[i]，w[i]均在int范围内$