King Terenas ordered his minister to design a brain-stimulating game for prince Arthas -- his son -- to improve his mental capabilities. The minister designed a game in which there are N boxes labeled 1,…,N; each box has a lock which can be opened only using its unique key. Before the game starts, the minister puts copies of the key of each box i
in the boxes i + 1 and i − 1, if they exist. Afterwards, D diamonds are placed inside D distinct boxes. Finally, all of the
boxes are locked and Arthas is given the keys to some M boxes. The Prince should collect all diamonds by opening the least number of boxes.
Arthas doesn't like too much thinking. "What are computers for, if we do the thinking?" he says. You are ordered by his
majesty, prince Arthas, son of the mighty king Terenas, to make the computer think and solve this task.
There are multiple test cases in the input. The first line of each test case starts with the integer N (1 <= N <= 109), the number of boxes, followed by M (1 <= M <= 100000), the number of keys given to Arthas, followed by D (0 <= D <= 100000), the number of diamonds. The M numbers on the next line represent the boxes whose keys are given to Arthas. Labels of the boxes containing the diamonds are listed on the next line. Labels in both two lines are given in increasing order, respectively. The input terminates with a line containing "0 0 0".
For each test case, write a single line containing the minimum number of boxes Arthas needs to open in order to collect all diamonds.
5 1 5 1 1 2 3 4 5 5 3 3 1 2 3 3 4 5 5 3 1 1 2 3 5 0 0 0
5 3 3
Migrated from old NTUJ.
2009Tehran
| No. | Testdata Range | Score |
|---|