Rin is conducting an experiment with some particles. Her particles are numbered from to , and each has a spin value . She observes her system of particles for time "ticks", and numbers the first tick . For each tick, she decides on three integers , , and , which she then uses to advance her experiment in one of two ways:

- If the tick is prime-numbered (i.e. , where is prime), she finds the sum of the spins values between particles and inclusive, and then adds to that sum. She then calls the resulting number the inefficiency of the system at tick .
- Otherwise, she increases the spins of each particle from to inclusive by .

Rin defines a cost of stopping the experiment at tick to be , where is prime (i.e., the cost is a tradeoff between the final inefficiency of the system and how many ticks it takes to get there). Help her find the minimum cost.

**Note:** to recall, a prime number is any natural number greater than 1 that has exactly two distinct factors.

#### Input Specification

The first line of input consists of two space-separated integers and . The next line will contain space-separated integers, indicating the spins of the th particle. lines follow, each containing three space-separated integers , , and .

#### Constraints

For all subtasks,

##### Subtask 1 [20%]

##### Subtask 2 [80%]

#### Output Specification

Output a single integer, the minimum cost of the experiment , for a prime .

#### Sample Input 1

```
6 4
162 840 327 543 957 582
5 5 329
3 5 -618
5 5 -242
2 5 -173
```

#### Sample Output 1

`3076`

#### Explanation

Rin achieves the minimum cost by stopping the experiment after the 2nd tick, when the inefficiency is 1538.

#### Sample Input 2

```
7 5
478 186 954 257 126 420 492
2 4 104
6 7 -63
5 6 619
1 5 -704
7 7 818
```

#### Sample Output 2

`1698`

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.

YOU'RE UNDER ARREST

It has come to our attention that you've been copying and pasting solutions on DMOJ as well as cheating on contests. This does not show good sportsmanship and is unfair to DMOJistan. Blindly copying and pasting code and cheating on contests does not improve your own abilities and breaks DMOJ's rules.

## Proof:

## Contest Cheating:

## Example 1: https://dmoj.ca/problem/ddrp3

eric574's submission: https://dmoj.ca/src/931485

Alternate accounts's submission: https://dmoj.ca/src/931158

Both joined contest at different windows.

## Example 2: https://dmoj.ca/problem/ppwindsor18p7

eric574's submission: https://dmoj.ca/src/1054225

Alternate accounts's submission: https://dmoj.ca/src/1054223

Both joined contest at different windows.

## Example 3: https://dmoj.ca/contest/dmopc17c2/ranking/

Note that eric574 solved the first problem in 37 seconds and the second one 1 minute 40 seconds, which wasn't achieved by IOI contestants and multiple others.

## Example 4: https://dmoj.ca/contest/tle17c2/ranking/

Note that eric574 solved the first problem in 21 seconds, which is only possible if he had read the problem beforehand.

The above has happened on multiple other occasions.

## Proof of Alternate Accounts

## Example 1: https://dmoj.ca/problem/dmopc18c2p3

Account 1's submission: https://dmoj.ca/src/1039154

Account 2's submission: https://dmoj.ca/src/1039335

Both joined contest at different windows, and were unrated for this contest, as they were confirmed to be the same person.

## Example 2: https://dmoj.ca/problem/mmcc14p3

Account 1's submission: https://dmoj.ca/src/819744

Account 2's submission: https://dmoj.ca/src/806968

From this (although there are multiple other examples), we know that eric574 is both reeee and _____.

In both contests mentioned, there was a previous entry of either reeee or _____ (this happens on almost all his contests).

## Code Copying:

## Example 1: https://dmoj.ca/problem/pacnw16j

Copied C++ Submission: https://dmoj.ca/src/1034737

Copied Python Solution: https://dmoj.ca/src/1029724

Source: http://speedyguy17.info/icpc/data/pacnw/2016/recap/Shopping/

## Example 2: https://dmoj.ca/problem/ccc10s5

Copied Solution: https://dmoj.ca/src/274408

Source: http://mmhs.ca/ccc/2010/S52010VLv2.txt

Again, there are multiple other examples, but I won't list them all.

Please refrain from doing this again.

## Note: His other submissions are generally edits of either wleung_bvg's code or kevinwen's code. This applies to anyone with a github account.

CopyPastePolice, YOU'RE UNDER ARREST

It has come to our attention that you've been copying and pasting solutions on DMOJ. This does not show good sportsmanship and is unfair to DMOJistan. Blindly copying and pasting code does not improve your own abilities and breaks DMOJ's rules.

## Proof:

## Example 1: Hello world - https://dmoj.ca/problem/helloworld

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/1454324

## Example 2: Hello world - https://dmoj.ca/problem/helloworldhard

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/279082

## Example 3: Hello world - https://dmoj.ca/problem/vmss7wc16c3p3

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/submission/1595568

## Example 4: Hello world - https://dmoj.ca/problem/tle18p1

Offender's Code: https://dmoj.ca/src/1021567

Source: https://dmoj.ca/src/1732316