Background

The full score for this problem is $70$.

Problem Description

In front of the strongman Karlo at the gym, there is an array $a$ of length $n$, where $a_i$ represents the weight of the $i$-th item. He can also use $k$ different “weight types”, numbered $1,2,\dots,k$.

For each weight type from $1$ to $k$, Karlo considers every item in the array in order and follows the process below:

1. Compute the result of dividing the item’s weight by the current weight type (discard the fractional part), and record this integer.
2. Multiply this integer by “the item’s weight $+2$”. If the resulting integer is greater than $10^8$, replace it with $10^8$.
3. Add up the integers obtained for all items to get the “strength value” of this weight type.

Karlo wants to know the sum of the strength values of all weight types. Please help him solve this problem.

Input Format

The first line contains two natural numbers $n,k$ ($1 \le n,k \le 10^5$), representing the number of items and the number of weight types.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^5$).

Output Format

Output one integer on a single line, representing the required total sum.

1 2
2

12

2 1
3 4

39

7 19
1 2 3 4 5 6 7

414

Hint

Sample Explanation

Explanation for Sample #2:

In this sample, there is only weight type $1$:

• $3 \to 3 \cdot (3+2)=15$
• $4 \to 4 \cdot (4+2)=24$

The total sum is $39$.

Subtasks

Translated by ChatGPT 5