Array Filling solution codechef

Array Filling solution codechef

You are given an array AA of size NN. Initially, the array is filled with 00-s.

There are MM types of operations that you can perform on array AA. The ithith operation can be described by two integers (xi,yi)(xi,yi). In this operation, you choose a set of indices SS such that

  • 1jN1≤j≤N,
  • (jmodyi)0(jmodyi)≠0,
  • Aj=0Aj=0,

, then you set Aj=xiAj=xi for all jSj∈S.

You can perform the operations in any order, but one type of operation can’t be done more than once. What is the maximum sum of integers of the array AA you obtain if you perform the MM operations optimally?

For example, consider the array A=[0,0,0,0]A=[0,0,0,0].

  • Suppose x=3,y=2x=3,y=2. Here you can choose indices 11 and 33 and set A1=A3=3A1=A3=3. So the array A becomes [3,0,3,0][3,0,3,0]. In this operation you can’t choose the indices 22 and 44 because (2mod2)=0(2mod2)=0(4mod2)=0(4mod2)=0.

  • Suppose x=5,y=3x=5,y=3 and you set A2=5A2=5. So the array AA becomes [3,5,3,0][3,5,3,0]. Here you can’t choose index 11 because A1>0A1>0 and index 33 because (3mod3)=0(3mod3)=0 and A3>0A3>0. However, you could also set A4=5A4=5.

  • Suppose x=4,y=4x=4,y=4. Now you can’t choose any index because Aj>0Aj>0 for all 1j31≤j≤3 and (4mod4)=0(4mod4)=0. So the array remains same.

Note: Since input-output is large, prefer using fast input-output methods.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each testcase contains M+1M+1 lines of input.
  • The first line of each test case contains two space-separated integers N,MN,M.
  • MM lines follow. For each valid ii, the ithith of these lines contains two space-separated integers xi,yixi,yi – parameters of the ithith operation.

Output Format

For each test case, output in a single line the maximum sum of integers of the array AA after MM operations.


  • 1T126001≤T≤12600
  • 1N1091≤N≤109
  • 1M1051≤M≤105
  • 1xi1091≤xi≤109
  • 2yi1092≤yi≤109
  • The sum of MM over all test cases does not exceed 106106.


Subtask #1 (100 points): original constraints

Sample Input 1 

10 1
5 2
8 2
5 2
6 3
3 2
2 2
1 3

Sample Output 1 



Test case 11: Optimal filling is [5,0,5,0,5,0,5,0,5,0][5,0,5,0,5,0,5,0,5,0].

Test case 22: Optimal filling is [6,6,5,6,6,0,6,6][6,6,5,6,6,0,6,6].

Test case 33: Optimal filling is [2,1,2][2,1,2].

Solution: Click here

Leave a Comment