问题1959--数组最大值

1959: 数组最大值

时间限制: 1 Sec  内存限制: 128 MB
提交: 206  解决: 24
[状态] [讨论版] [提交] [命题人:]
题目描述

有一个数组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以增序给出。
保证输入合法

输出

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

样例输入 Copy
1
10 3
4 2
5 6
9 3
样例输出 Copy
5
来源/分类