The Prosecutor's Proposal


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 500M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

15 years ago, Lee Gil Young, for 1 million won, sent his best friend Kang Woo Sung to the afterlife... leaving Kang Tae Seon and Lee Chae Ha to live under the shadow of public scrutiny and haunting memories.

15 years later,

The first proposal: Investigator Lee Chae Ha comes to work at prosecutor Ju Tae Seon's office. ...

The case of Director Kang Woo Sung is reopened, and the real culprit turns out to be Mrs. Oh Ja Hyun, the second daughter of the Ohsong Group, along with her longtime lover — meaning Lee Gil Young's innocence is finally restored.

The second proposal: "Go out with me, Lee Chae Ha!" ...

Prosecutor Kang then quickly uses handcuffs to lock the two of them together, keeping Lee Chae Ha close by his side. The handcuffs were taken from the other person's bag. A habit from his days as a police officer meant he always kept a spare pair of handcuffs in his bag.

However, after talking for a while, the two realize that these handcuffs don't actually belong to investigator Lee — they had been swapped at some point by team leader Song. And now, they can't unlock them.

This pair of handcuffs is made from N links. Each link has a durability \(a_i\). To break it, they need to physically strike K contiguous segments of links, such that no link is struck more than once. The force required to strike a segment \(b_1, b_2, ..., b_M\) is \(gcd(b_1, b_2, ..., b_M) + P \times M\).

How many units of force do they need to break these handcuffs?

"I do respect Lee Chae Ha's hobbies~"

Data

  • The first line contains three positive integers \(N, K, P \ (1\le K \le N \le 10^3; 1\le P\le 10^3)\);
  • The second line contains \(N\) integers \(a_i \ (1\le a_i \le 10^6)\).

Result

  • The answer to the problem.

Scoring

  • Subtask 1 (20%): \(K = 1\).
  • Subtask 2 (40%): \(N \le 100\).
  • Subtask 3 (40%): No additional constraints.

Example

Example 1

input

10 2 1
16 16 16 8 8 8 4 4 4 2

output

8

Explanation

Choose the two segments \([a_8]\) and \([a_{10}]\).


Comments

There are no comments at the moment.