【問題G20】魔術數字。            [回前頁]

每當職棒球季進行到尾聲，球隊間互相為了獲得冠軍而廝殺之際，魔術數字便成為棒球迷的焦點。到底什麼是魔術數字呢？魔術數字什麼時候點亮？魔術數字要怎麼計算？請看以下的介紹。

一個聯盟中有許多球隊要爭取排名第一的位子。將球隊的勝場數除以已賽場次即可得到勝率，而球隊之間的戰績排行就以勝率為依據來做比較。假設戰績領先隊為A隊，其對B隊的魔術數字mAB存在的意義在於，B隊已經無法自力阻止A隊封王。若B隊剩餘賽程全勝時(包括對A隊所有剩餘賽事皆獲得勝利)，而A隊只需要對其他隊伍共贏得mAB場比賽，mAB小於或等於(A隊所剩的比賽場次 – A隊與B隊剩餘對戰場次)，使A隊在戰績排行上仍然領先B隊的話，則我們會說A隊對B隊的魔術數字已點亮，而點亮的魔術數字即是mAB。若mAB大於(A隊所剩的比賽場次 – A隊與B隊剩餘對戰場次)時，此時A隊對B隊的魔術數字尚未出現。換句話說，B隊只要一鼓作氣連勝到底，戰績就可以超越或追平A隊，不需要巴望著A隊敗給其他球隊。

舉例來說明魔術數字的計算方法：A隊應賽50場，已賽35場，戰績26勝9敗，勝率0.743。B隊應賽50場，已賽34場，戰績20勝13敗1和，勝率0.606。而A隊與B隊剩餘賽程為3場。要計算A隊對B隊的魔術數字mAB，先假設落後隊B隊剩餘賽程全勝，也就是B隊贏得剩餘16場比賽，戰績36勝13敗1和，勝率0.735。而A隊輸掉3場與B隊的對戰，戰績26勝12敗，剩餘賽事15-3=12場。以討論的方式來檢查A隊至少要再贏m場，勝率就必定超過B隊。

由於討論所得到的m為11，小於12 (A隊剩餘場次 – A隊與B剩餘對戰場次=15-3=12)，因此A隊對B隊魔術數字已點亮，且魔術數字為11。當A隊對B隊的魔術數字歸零時，表示B隊的戰績已經篤定無法超越A隊(與冠軍無緣)了。一般而言，只有領先隊伍與第二名隊伍間的魔術數字較為常用。但實際上，領先隊對所有其他隊伍都可能存在一個魔術數字。今天，你的任務是寫一個魔術數字計算程式。輸入每個球隊的隊名，戰績，和球隊間的剩餘對戰場次，你的程式除了能依球隊戰績排行輸出戰績表以外，還可以將求得的魔術數字輸出。

輸入檔說明

輸入檔可能包含多筆的測試資料。

每一筆測試資料的第一行有兩個數字n和g。第一個數字n (2<=n<=6)表示聯盟的球隊數。第二個數字g (10<=g<=100)則表示一個球隊在一個球季應出賽場次。第二行開始一共n行，每一行依序包含了一隻球隊隊名，勝場數，和局數，敗場數。球隊的隊名由英文字母組成，最長為9個字母。勝場數，和局數，和敗場數皆為正整數，且其和不會超過g。(你可以假設n隻球隊中，必定只有一支球隊勝率最高。)

假設各球隊依在上述資料中出現順序分別編號為1,2,…,n。在接下來的n行中，每一行有n個數字。第i行的第j個數字表示第i支球隊與第j支球隊的剩餘場數(1<= i,j <=n)。你可以假設測試資料都是合乎常理的數字，反映現實生活中計算魔術數字的情形。例如第i行的第i個數字一定為0，因為自己球隊不可能跟自己球隊打。而第i行的第j個數字必定等於第j行的第i個數字。另外，一支球隊的對各隊的剩餘場數加上該球隊的已勝場數，和局數，以及已敗場數必定等於g。

當測試資料第一行的輸入n和g皆為0時，表示測試資料全部結束，程式不需要對這行輸入作處理。

輸出檔說明

對於每一筆測試資料，請輸出一排版過的戰績表。依n支球隊的戰績排名順序輸出n行。除了第1名球隊以外，若發生勝率相同的情形，請依球隊在原資料的出現順序為輸出順序，但其排名則應並列。格式請參考範例輸出。隊名，勝率，魔術數字分別以一個空格來間隔，而隊名部分不足9個字元的部分則需填入空格。勝率固定輸出到小數點後三位(四捨五入)。第一名球隊不需要輸出魔術數字，請你分別計算出第一名球隊對其他球隊的魔術數字。若對其他球隊的魔術數字尚未點亮，請輸出”--”。若魔術數字已點亮，則輸出”M”以及該數字。測試資料之間請留一個空行。

範例輸入

範例輸出