Frog Jumping
Limits: 3 sec., 256 MiB
Marichka and Zenyk like romantic evenings. Today they decided to watch frogs jump over stones.
There are \(n\) stones placed in a line and numbered from the left to the right using integers from 1 to \(n\), inclusive. The distance between any two consecutive stones is exactly 1 meter.
There are also \(m\) frogs, initially located on the first stone. The objective is to move all frogs to the last (\(n\)-th) stone by jumping. Each frog can only jump forward.
The following two condition must be fulfilled:
Stones \(a_1\), \(a_2\), ..., \(a_k\) must be visited by exactly one of the frogs.
All the other stones (except the first one and the last one) must be never visited by any frog.
When the \(i\)-th frog jumps more than \(d\) meters in a single jump, it costs \(c_i\) units of energy. Any smaller jump costs nothing.
Your task is to find the minimum total amount of energy needed for all frogs to get to the last stone.
Input
The first line of the input contains four space-separated integers \(n\), \(m\), \(k\) and \(d\). The second line contains \(m\) space-separated integers \(c_i\), which are the energy costs of a big jump for the corresponding frogs. The third line contains \(k\) space-seperated unique integers \(a_i\), which are the indices of stones that must be visited exactly once.
Output
In the first and only line of the output print a single integer — minimum total energy cost.
Constraints
\(3 \le n \le 10^9\),
\(1 \le m, k \le 10^5\),
\(1 \le d, c_i \le 10^9\),
\(2 \le a_i < n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 10 2 3 3 4 7 4 8 7 | 4 |
| Input (stdin) | Output (stdout) |
|---|---|
| 10 2 2 3 4 7 9 5 | 15 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|