图形排版 ### 题目描述 小明需要在一篇文档中加入 $N$ 张图片，其中第 $i$ 张图片的宽度是 $W_i$，高度是 $H_i$。 假设纸张的宽度是 $M$，小明使用的文档编辑工具会用以下方式对图片进行自动排版： 1\. 该工具会按照图片顺序，在宽度 $M$ 以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在 $M=10$ 的纸张上依次打印 3x4, 2x2, 3x3 三张图片，则效果如下图所示，这一行高度为 4。(分割线以上为列标尺，分割线以下为排版区域；数字组成的矩形为第 $x$ 张图片占用的版面) 0123456789 \---------- 111 111 333 11122333 11122333 2.如果当前行剩余宽度大于 0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张 4x9 的图片，由于剩余宽度是 2，这张图片会被压缩到 2x5，再被放入第一行的末尾。此时该行高度为 5： 0123456789 \--------- 44 111 44 111 33344 1112233344 1112233344 3.如果当前行剩余宽度为 0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度和就是这 $N$ 张图片的排版高度。例如再放入 11x1, 5x5, 3x4 的图片后，效果如下图所示，总高度为 11： 0123456789 \---------- 44 111 44 111 33344 1112233344 1112233344 5555555555 66666 66666777 66666777 66666777 66666777 现在由于排版高度过高，图片的先后顺序也不能改变，小明只好从 $N$ 张图片中选择一张删除掉以降低总高度。他希望剩余 $N-1$ 张图片按原顺序的排版高度最低，你能求出最低高度是多少么？ ### 输入描述 输入描述 第一行包含两个整数 $M,N$，分别表示纸张宽度和图片的数量。 接下来 $N$ 行，每行 2 个整数 $W_i,H_i$，表示第 $i$ 个图大小为 $W_i \times H_i$。 其中,$1 \leq N \leq 10^5$，$1 \leq M, W_i, H_i \leq 100$。 ### 输出描述 一个整数，表示在删除掉某一张图片之后，排版高度最少能是多少。 ### 输入输出样例 #### 示例 > 输入 ```txt 4 3 2 2 2 3 2 2 ``` > 输出 ```txt 2 ```