有一个数组a[]，它的初始下标为1，我们不知道这个数组里的元素，但知道这个数组满足以下几个性质：
①长度为n，且a[1]=0，a[]中所有的数都是非负整数;
②任意两个相邻元素差的绝对值不大于1，比如a[1]=4，那么a[2]的值只可能是3,4,5中的一个
③对于部分的特殊点xi，满足a[xi]<=ki，这样的点共m个
问数组a[]中的最大值最大可能为多少？

多组测试数据，第一行一个整数T(<=10)，表示测试数据数量
每组数据第一行两个整数n，m，表示a[]的长度与特殊点的个数，其中1<=N<=100000, 0<=M<=50.
之后M行，每行两个整数xi与ki，其中1<=xi<=n,0<=ki<=100000，且xi以增序给出。
保证输入合法

每组输入一个数表示数组中的可能最大值