Bribe the Prisoners (Small)

Interview

Time limit5sMemory limit512 MB

Summary

Choose the release order of Q prisoners out of P cells to minimize total bribes, where each release bribes every still-occupied prisoner reachable from it until a boundary or empty cell.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Recursion, Intervals
Solved: No attempts yet

Problem

A kingdom has $P$ prison cells built in a straight line and numbered 1 to $P$ . Cell $i$ and cell $i+1$ are adjacent, and the prisoners in two adjacent cells are neighbours. A wall with a window separates adjacent cells, so neighbours talk to each other through the window.

Everyone stays calm until a prisoner is released. When that happens, both neighbours of the released prisoner find out, and each of them passes the news to his own other neighbour. That prisoner passes it on again, and the news keeps travelling until it reaches a prisoner who has no further neighbour, either because he is in cell 1, or because he is in cell $P$ , or because the next cell is already empty. A prisoner who learns that someone was released smashes everything in his cell unless he is handed one gold coin. So releasing the prisoner in cell $A$ forces you to bribe every prisoner on both sides of cell $A$ , up to cell 1, up to cell $P$ , or up to an empty cell.

Every cell holds exactly one prisoner at the start, and only one prisoner is released per day. Given the $Q$ prisoners to release over $Q$ days, find the smallest total number of gold coins you need if you may choose the release order freely.

A bribe works for one day only. A prisoner bribed yesterday must be bribed again if he hears about another release today.

Input

The first line holds the number of test cases $N$ . $N$ test cases follow. Each case takes two lines. The first line is

P Q

where $P$ is the number of prison cells and $Q$ is the number of prisoners to release. The second line holds $Q$ distinct cell numbers, space separated, sorted in ascending order.

Limits

$1 \le N \le 100$
$1 \le P \le 100$
$1 \le Q \le 5$
$Q \le P$
Every cell number is between 1 and $P$ , inclusive.

Output

For each test case, print one line in the format

Case #X: C

where $X$ is the case number starting from 1, and $C$ is the minimum number of gold coins needed for the bribes.

Note

Take $P = 20$ , $Q = 3$ and the cells 3, 6, 14. Releasing cell 14 first, then cell 6, then cell 3 costs $19 + 12 + 4 = 35$ . Releasing cell 6 first, then cell 3, then cell 14 costs $19 + 4 + 13 = 36$ .

Examples5

Example 1

Input

Expected output

Case #1: 7
Case #2: 35

Example 2
Input
```
1
1 1
1
```
Expected output
```
Case #1: 0
```

Example 3

Input

Expected output

Case #1: 99
Case #2: 99
Case #3: 99

Example 4
Input
```
1
5 5
1 2 3 4 5
```
Expected output
```
Case #1: 6
```
Example 5
Input
```
1
2 2
1 2
```
Expected output
```
Case #1: 1
```