tycho (BOI contest)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: shortest path, modular arithmetic, dynamic programming

# Tycho
Problem ID: tycho

The planetary exploration vehicle *Tycho VIII* needs to get back to the home base after collecting mineral samples. Tycho travels in a straight line from position 0 to the home base at position *b*. While moving, it advances at a slow but steady pace of 1 unit per second. Every second, Tycho takes 1 unit of environmental damage from the harsh planetary conditions.

The situation is made even worse by radiation from a nearby pulsar, which adds *d* additional units of damage every *p* seconds. However, the radiation damage can be avoided by seeking shelter in one of *n* different hiding spots—caves, vegetation, large rocks,

![](_page_0_Picture_3.jpeg)

carcasses of the planet's megafauna—along the way. Tycho can choose to stand still at any point for any integer number of seconds.

The starting position 0 and the home base at *b* are both sheltered, so Tycho takes no radiation damage there.

What is the minimum damage Tycho will take on its journey back to the home base?

## Example

Consider the situation where the home base is at position 18 and there are shelters at positions 8 and 15.

![](_page_0_Figure_9.jpeg)

Assume that the pulsar's period is 4, so unsheltered Tycho would take damage at times 4, 8, 12, etc. If Tycho leaves from the starting position (where it's sheltered) at time 0, it can reach the first shelter after 8 seconds, incurring radiation damage *d* at time 4 (but none at time 8 because it's sheltered then). Continuing without stopping, it reaches the home base at time 18, incurring *d* + *d* more units of radiation damage (at times 12 and 16, respectively). This way it incurs *d* + *d* + *d* = 3*d* units of radiation damage and 18 units of environmental damage. If instead Tycho waits at the 2nd shelter (at position 15) for 1 second, the pulse at time 16 causes it no damage, and it reaches the home base at time 19 with a total of 2*d* + 19 units of damage. This is better for most values of *d*. The two situations are shown here:

![](_page_0_Figure_11.jpeg)

If the pulsar's period is 10, Tycho can wait at the starting position for 2 seconds and then just go home without stopping at any shelter. Thus it passes the 1st shelter (at position 8) at just the right moment when the pulsar flares and arrives at the home base at time 20, for a total of 20 environmental damage and no radiation damage at all.

![](_page_0_Figure_13.jpeg)

### Input

The first line consists of four integers *b*, *p*, *d*, and *n*, separated by single spaces: the location *b* of the home base, the pulsar's flare period *p*, the additional radiation damage *d* caused by each flare of the pulsar, the number *n* of the shelters.
The following *n* lines each contain an integer giving the shelter locations $a_1, ..., a_n$, with $0 < a_1 < \dots < a_n < b$.

### Output

Print a single integer: the minimum amount of damage Tycho must take to reach *b*.

## Constraints and Scoring

You can assume *p* < *b* and *n* < *b*. We always have $1 \le b \le 10^{12}$, $0 \le d \le 10^6$, and $0 \le n \le 10^5$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

| Group | Points | Constraints                                                              |
|-------|--------|--------------------------------------------------------------------------|
| 1     | 8      | $p \le 10^6$ and Tycho does not need to wait after leaving position 0.* |
| 2     | 5      | $b \le 1000$, $p \le 100$, $n \le 10$                                  |
| 3     | 7      | $b \le 1000$                                                             |
| 4     | 15     | $p \le 10^6$, $n \le 1000$                                              |
| 5     | 20     | $p \le 100$                                                              |
| 6     | 35     | $p \le 10^6$                                                              |
| 7     | 10     | No additional constraints                                                |

\* In test group 1, Tycho may still need to wait at position 0 *before* it starts moving. For example, sample inputs 2, 3, and 4 belong to test group 1.

| Sample Input 1 | Sample Output 1 |
|----------------|-----------------|
| 18 4 5 2       | 29              |
| 8              |                 |
| 15             |                 |

| Sample Input 2 | Sample Output 2 |
|----------------|-----------------|
| 18 4 0 2       | 18              |
| 8              |                 |
| 15             |                 |

| Sample Input 3 | Sample Output 3 |
|----------------|-----------------|
| 18 10 100 2    | 20              |
| 8              |                 |
| 15             |                 |

| Sample Input 4 | Sample Output 4 |
|----------------|-----------------|
| 18 4 100 0     | 418             |

| Sample Input 5 | Sample Output 5 |
|----------------|-----------------|
| 65 20 100 3    | 172             |
| 14             |                 |
| 25             |                 |
| 33             |                 |

Starter code:

Grader code:

Setup script:

Evaluation script: