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

**Task**

You are given an array * A* of size

*. Initially, the array is filled with 0-s.*

**N**There are * M* types of operations that you can perform on array

*. The*

**A***operation can be described by two integers*

**i**^{th}**(**. In this operation, you choose a set of indices S such that

*x*,_{i}*y*)_{i}**1 ≤ j ≤ N**,**(j mod***y*_{i})≠0,*A*_{j}= 0,

, then you set ** A_{j}=x_{i} **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

*operations optimally?*

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

- Suppose
. Here you can choose indices*x*= 3,*y*= 2**1**and**3**and set. So the array A becomes*A*1 =*A*3 = 3**[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. So the array*A*_{2}= 5becomes*A***[3, 5, 3, 0]**. Here you can’t choose index**1**becauseand index*A*_{1}> 0**3**because**(3 mod 3)=0**and*A*_{3}> 0.*A*_{4}= 5 - Suppose
. Now you can’t choose any index because*x*= 4,*y*= 4for all*A*>0_{j}**1 ≤**and*j*≤ 3**(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
denoting the number of test cases. The description of**T**test cases follows.**T** - Each testcase contains
lines of input.*M*+ 1 - The first line of each test case contains two space-separated integers
.*N, M* - M lines follow. For each valid
, the**i**of these lines contains two space-separated integers**i**^{th}– parameters of the*x*_{i},y_{i}operation.**i**^{th}

**Output Format**

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

*operations.*

**M****Constraints**

**1 ≤***T*≤ 12600**1 ≤***N*≤ 10^9**1 ≤***M*≤ 10^5**1 ≤***x*≤ 10^9_{i}**2 ≤***y*≤ 10^9_{i}- The sum of
over all test cases does not exceed*M***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**

**C++**

**Python**

**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.