题目描述

小灰灰和小东东在玩一种竞技游戏。在游戏中，小灰灰给小东东由 n 个正整数组成的序列以及 m 条操作指令，需要小东东按照指令来对 n 个整数进行操作。其中每条指令都包括二个整数 ( a , b )，意义如下：

如果 a 大于 0 ，表示将序列中第 b 个数乘于 2 ；

如果 a 小于 0 ，表示将序列中第 b 个数加上 2 ；

如果 a 等于 0 ，则忽略此条指令。

游戏结束后，小东东需要求出序列中的最大值。现在小东东求助于你，希望你能用计算机编程求出他需要的答案。题目保证计算结果在 int 的表示范围内。

输入格式

第一行为一整数 T ，表示有 T 组数据。

每组输入数据第一行有二个整数 n, m, (1 <= n <= 100 , 1 <= m <= 100 )

第二行有 n 个整数 ( 1 ~ 100 ) ，表示初始序列,编号从1...n。接着是 m 行表示 m 条指令，每行共有 2 个用空格隔开的整数 a b , ( -50 <= a <= 50 , 1 <= b <= n )。

输出格式

对于每组数据，输出一个整数占一行，表示操作后的序列中的最大整数。

样例

2
2 2
1 2
1 1
-1 2
3 4
1 5 6
1 1
1 1
0 1
-1 1

4
6