Array Filling | CodeChef Solution

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 N. Initially, the array is filled with 0-s.

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

• 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 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 A₂ = 5. So the array A becomes [3, 5, 3, 0]. Here you can’t choose index 1 because A₁ > 0 and index 3 because (3 mod 3)=0 and A₃ > 0. However, you could also set A₄ = 5.
• Suppose x = 4, y = 4. Now you can’t choose any index because A_j>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 i^th of these lines contains two space-separated integers x_i,y_i – parameters of the i^th 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 ≤ x_i ≤ 10^9
• 2 ≤ y_i ≤ 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

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.