题目描述

酒瓶永远不会被完全装满，因为要防止热胀冷缩，酒瓶顶部必须留有少量的空间。
当酒瓶中的留的空间过小时，酒可能会受热膨胀，导致瓶塞被挤开，然后酒就会变质；
当酒瓶中的留的空间过大时，酒就可能会变质。
因此，每个瓶子都有一个最大容量和最小容量。
现在给你一定量的酒和几个瓶子。
你需要把酒装入其中几个瓶子，在酒不变质的情况下尽可能多装一些酒。

输入

第一行输入一个正整数 $n$，表示有 $n$ 组测试数据；
每组测试数据中 第一行输入两个正整数 $h$ , $m$ 表示有　$h$ 升的酒和 $m$ 种酒瓶。
之后 $m$ 行每行输入两个正整数 $a$ , $b$ , 表示酒瓶的最小容量和最大容量。
每组测试数据之间有一行空行
每种瓶子的数量是无限的

输出

对于每组测试数据，输出一行一个非负整数，表示不能装瓶的酒。
输出剩余的酒的单位是ml

范围/提示

$0L \le h \le 1000000L$ ;
$1 \le m \le 100$
$1 \le n \le100$ ;
$325ml \le a \le b \le 4500ml$;
$95\%a \le b \le 99\%a$.