2013年7月18日 星期四

1064 - Network

網路的封包交換處理在一個小單位上,將一個長訊息(message)  分成多個封包(packet)由不同的路徑傳遞,由於不同的路徑,抵達的時間也會有所不同,同時順序也會被改變。而在接收端的電腦將原本的訊息組合正確。

接收段的電腦使用一個緩衝區去接收不按照順序進入的封包,計算最小的緩衝區大小去組合所有進來的訊息,根據訊息的數量(N)、封包的數量(M)、以及封包接收的順序寫程式計算之。


當每個封包抵達時,會進入緩衝區或直接進入輸出區這兩種可能,所有封包可以在任何時間從緩衝區得到。而一個封包可以離開緩衝區,意即直接進入輸出區,而一個訊息離開緩衝區則是當它的所有封包已經離開緩衝區。


每個訊息的封包必須按照原本的順序通過緩衝區,例如封包具有訊息的 byte 3 到 5,一定會在另一個封包具有訊息的 byte 6 到 10 前抵達輸出區。而每個訊息也必須按照順序抵達輸出區,而哪個訊息要先被處理,可以由自己決定。但是單一訊息的封包一定要按照順序地通過緩衝區進入輸出區。不用想像真實的緩衝系統,假想可以事先知道封包的進入順序。


每個封包具有資料以及 header,header 有三個整數:第一個整數是訊息的編號,第二整數是開始的 byte 編號,第三個整數是結束的 byte 編號。每個訊息的第一個 bytes 編號為 1。
例如:如下圖有 3 個訊息(長度分別為 10, 20, 5 bytes),而總共有 5 個封包,最小的緩衝區大小為 10,封包#1 與封包#2 先存入緩衝區,兩個共有 10 bytes,而封包#3 直接進入輸出區(完成訊息#3的傳遞),封包#4 也直接進入輸出區,接著換封包#2 離開緩衝區(完成訊息#1 的傳遞),最後封包#5 直接進入輸出區,接著封包#1 離開緩衝區(完成訊息#1的傳遞)。

Input 

輸入有多組測資。

每組第一行有兩個整數 N, M (1 <= N <= 5, 1 <= M <= 1000),分別表示訊息數量以及封包數量。第二行則會有 N 個整數表示訊息#1 的總長度、訊息#2 的總長度 ... 類推。而接下來會有 M 個封包訊息,每個封包有三個整數,訊息編號、起始與結束的 byte 編號。

每個封包大小不超過 64 bytes。

N = M = 0 結束程式。

Output 

對於每組測資,輸出測資組編號,以及一個最小的緩衝區大小。

每組測資後,輸出一行空行。

Sample Input 

3 3 
5 5 5 
1 1 5 
2 1 5 
3 1 5 
3 5 
10 20 5 
2 16 20 
1 6 10 
3 1 5 
1 1 5 
2 1 15 
0 0

Sample Output 

Case 1: 0 

Case 2: 10