该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意

本题需要使用文件读写（entries.in / entries.out）。

题目背景

Sleeping Jellyfish 是一位特别毒瘤的老师，它时常在学校的 OJ 里面添加一些特别毒瘤的题，但有些能过，有些不能过。

题目描述

Sleeping Jellyfish 有 $n$ 分钟的空闲时间。

它同时收到了 $m$ 道题目投稿，第 $i$ 道题目的难度为 $w_i$，需要 $t_i$ 分钟审核。

那么它能审核完的题目的难度之和最大为多少？

输入格式

第一行两个正整数 $n, m\ (1 \le n, m \le 600)$。

下面 $m$ 行，每行两个正整数 $t_i, w_i\ (1 \le t_i, w_i \le 10)$。

输出格式

一行一个非负整数，表示在规定时间内审核完的题目总权值的最大值。

样例

23 4
9 7
4 2
1 1
10 10

19