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