234 - Switching Channels

Switching Channels

CPN (The Couch Potato Network) 擁有許多有線頻道，他們要安排節目的時間，好讓觀眾不會錯過節目，為了做到這一點，發們發現有一個 對齊點 (alignment point) 相當重要，理想的情況時，每個對齊點恰好是一個心的節目開始，而有些對齊點又特別重要，例如晚間新聞的時間點就相當重要。當觀眾知道節目表後，他們可能會少看一些 CPN 節目！因為可能會少看到節目的一部分，或者是要等待上一個節目結束，而這段時間稱為 miss time。而你被雇用來找到一個最恰當的節目安排方式。

miss time 的定義為對齊點與最鄰近的節目開始或節目結束差的絕對值，而 total miss time 則是在相同重要程度的對齊點的 miss time 總和。一個節目安排方式優於另一個節目的安排方式，是先比較最重要的 total miss time，再比較次重要的 total miss time ... 類推。

Input

每組測資會有一個整數 p (0 <= p <= 8)，表示節目的個數。
每組測資的時間點從 0 開始，接下來則會有 p 個整數表示節目的長度(單位為分鐘)。

接下來會有一個整數表示對齊點的個數 a (0 <= a <= 8)，每組對齊點有兩個整數 i, t，
(1 <= i <= 5)，i 表示重要程度，1 表示最重要，2 表示第二重要 ... 類推。而 t 則表示對齊的時間點，且不會有兩個對齊點具有相同的 t。

Output

對於每組測資，輸出一行測資組編號，格式如下：

Data set n
接著輸出最佳的節目編排方式， 以及輸出所有的 total miss time 的總和。
如果有多組最佳的節目編排方式，則任何一組都可以。

Sample Input

4  30 45 45 15
3  1 60  2 90  3 15
6  10 15 13 18 25 33
4  1 30  2 15  2 45  1 60
0

Sample Output

Data set 1
Order: 15 45 30 45 
Error: 0
Data set 2
Order: 15 13 33 25 18 10
Error: 19

範例輸入解釋

Data set 2
Order: 15 13 33 25 18 10
Error: 19

得到節目的時間點為 0, 15, 28, 61, 86, 104, 114。
對於最重要的時間點 30, 60
30 最鄰近的時間為 28，miss time = |30-28| = 2

60 最鄰近的時間為 61，miss time = |60-61| = 1
total miss time = 2+1 = 3
對於次重要的時間點為 15, 45

15 最鄰近的時間為 15，miss time = |15-15| = 0

45 最鄰近的時間為 61，miss time = |45-61| = 16
total miss time = 0+16 = 16
=> Error = 3+16 = 19