题目描述

葡萄酒瓶从不会被完全装满：必须在瓶颈处保留少量空气以应对热胀冷缩。若保留空气过少，酒液膨胀可能导致软木塞弹出；若保留空气过多，酒液可能变质。因此每个酒瓶都有最小和最大容量限制。

给定一定量的葡萄酒和若干种不同规格的酒瓶，请确定选用哪些酒瓶能使每个酒瓶的装量都在其最小和最大容量之间，并尽可能多地装瓶葡萄酒。

输入格式

第一行输入包含两个整数：待装瓶的葡萄酒量（以升为单位，范围$0-1,000,000$）和酒瓶规格数量（范围$1-100$）。随后每行输入给出一种规格酒瓶的最小和最大容量（以毫升为单位）。最大容量不小于$325$毫升且不超过$4500$毫升。最小容量不小于最大容量的$95$%且不大于$99$%。假设每种规格酒瓶供应充足。

输出格式

输出应为单个整数：表示无法装瓶的葡萄酒量（以毫升计）。

输入样例1

10 2
4450 4500
725 750

输出样例1

250

输入样例2

10000 2
4450 4500
725 750

输出样例2

0

来源
Waterloo local 1999.10.02