THE PROBLEM STATEMENT:
There are many sub-networks connected together by switches. Each switch has number of nodes connected to it.
There was a new song uploaded on the internet. This news spreads all over the network, so, everyone starts downloading this new song as soon as they find out about it. The traffic on each switch is increasing every second as more and more nodes start receiving the packets from that switch.
Traffic on a switch is proportional to nodes (users) downloading the file at that switch. At each second more and more nodes (users) are connecting to the network to download the song.
Suppose each switch is assigned an identity, id. At a particular second, n nodes are connected to the network and n switches are used by these nodes for transfer of data.
The n nodes use the switches in a manner as stated below:
You are given the identity, id of the starting switch =a.
1st node uses switch a.
2nd node uses switch a+1.
3rd node uses switch a+2.
.......
Nth node uses switch a+n-1.
The above process of addition of nodes happens at that particular second.
There are q such seconds and n nodes are added at each of these q seconds using the method given above. It takes infinite time to download the file. After q seconds, each switch will have different number of nodes connected to it. Your task is to find maximum of these number of nodes. In other terms the maximum traffic at an instant after q seconds.
Initially, there is no traffic in the network.
INPUT:
The first line of input contains the number of test cases t.
1. For each test case, the first line contains an integer p, the number of switches.
The id of each switch 1 is 1, 2 is 2 and so on for all p switches.
2. The second line contains the number of seconds (q).
3. Then q lines follow, 1st line contains the query for 1st second, line two for 2nd second and so on. Each line contains 2 integers, n and a, where n is the number of nodes that connect to the network at that second and a is the starting id of the switch.
OUTPUT:
Output a line for each test case containing an integer, the answer, the maximum traffic for that test case.
CONSTRAINTS:
1<=t<=100
1<=p<=105
1 <= a<=105
1<=n<=105
1<=q<=105
a+n<=p
Problem Code: MAXTRAF
Author and Tester: Prateek Kumar
In the sample test case p=5, i.e., 5 switches are there with identities 1,2,3,4,5
q=3, Meaning query for 3 different seconds For second 1: n=4 a=1 Number of node at switches after n=1, Switch identity -------------- 1 2 3 4 5 No. of connected nodes-- 1 1 1 1 0
For second 2: n=2 a=2 Number of node at switches after n=1, Switch identity -------------- 1 2 3 4 5 No. of connected nodes-- 1 2 2 1 0
For second 3: n=1 a=2 Number of node at switches after n=1, Switch identity -------------- 1 2 3 4 5 No. of connected nodes-- 1 3 2 1 0
You can see that the maximum nodes are connected to switch 2, therefore, the answer after q queries is 3.
