题目描述

小明需要在一篇文档中加入 $N$ 张图片，其中第 $i$ 张图片的宽度是 $W_i$ ，高度是 $H_i$ 。

假设纸张的宽度是 $M$ ，小明使用的文档编辑工具会用以下方式对图片进行自动排版：

该工具会按照图片顺序，在宽度 $M$ 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 $M=10$ 的纸张上依次打印 $3 \times 4$ , $2 \times 2$ , $3 \times 3$ 三张图片，则效果如下图所示，这一行高度为 4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第 $x$ 张图片占用的版面)

0123456789

111

111 333

11122333

如果当前行剩余宽度大于 0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张 $4 \times 9$ 的图片，由于剩余宽度是 2，这张图片会被压缩到 $2 \times 5$ ，再被放入第一行的末尾。此时该行高度为 5：

0123456789

111 44

111 33344

1112233344

如果当前行剩余宽度为 0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 $N$ 张图片的排版高度。例如再放入 $11 \times 1$ , $5 \times 5$ , $3 \times 4$ 的图片后，效果如下图所示，总高度为 11：

0123456789

111 44

111 33344

1112233344

5555555555

66666

66666777

现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 $N$ 张图片中选择一张删除掉以降低总高度。他希望剩余 $N-1$ 张图片按原顺序的排版高度最低，你能求出最低高度是多少么？

输入描述

第一行包含两个整数 $M,N$ ，分别表示纸张宽度和图片的数量。

接下来 $N$ 行，每行 2 个整数 $W_i,H_i$ ，表示第 $i$ 个图大小为 $W_i×H_i$ 。

其中, $1≤N≤10^5$ ， $1≤M,W_i,H_i≤100$ 。

一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。