# Array Filling | CodeChef Solution

Hello coders, today we are going to solve Array Filling CodeChef Solution whose Problem Code is ARRFILL.

Contents

## Task

You are given an array A of size N. Initially, the array is filled with 0-s.

There are M types of operations that you can perform on array A. The ith operation can be described by two integers (xi, yi). In this operation, you choose a set of indices S such that

• 1 â‰¤ j â‰¤ N,
• (j mod yi)â‰ 0,
• Aj = 0,

, then you set Aj=xi for all j âˆˆ 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 A you obtain if you perform the M operations optimally?

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

• Suppose x = 3, y = 2. Here you can choose indices 1 and 3 and set A1 = A3 = 3. So the array A becomes [3, 0, 3, 0]. In this operation you can’t choose the indices 2 and 4 because (2 mod 2)=0, (4 mod 2)=0.
• Suppose x = 5, y = 3 and you set A2 = 5. So the array A becomes [3, 5, 3, 0]. Here you can’t choose index 1 because A1 > 0 and index 3 because (3 mod 3)=0 and A3 > 0. However, you could also set A4 = 5.
• Suppose x = 4, y = 4. Now you can’t choose any index because Aj>0 for all 1 â‰¤ j â‰¤ 3 and (4 mod 4) = 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 T denoting the number of test cases. The description of T test cases follows.
• Each testcase contains M + 1 lines of input.
• The first line of each test case contains two space-separated integers N, M.
• M lines follow. For each valid i, the ith of these lines contains two space-separated integers xi,yi – parameters of the ith operation.

## Output Format

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

## Constraints

• 1 â‰¤ T â‰¤ 12600
• 1 â‰¤ N â‰¤ 10^9
• 1 â‰¤ M â‰¤ 10^5
• 1 â‰¤ xi â‰¤ 10^9
• 2 â‰¤ yi â‰¤ 10^9
• The sum of M over all test cases does not exceed 10^6.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input

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

Sample Output 1

``````25
41
5
``````

Explanation

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

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

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

## Solution – Array Filling

### Java

Disclaimer: The above Problem (Array Filling) is generated by Hacker Rank but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.