鞋匠有 𝑁 件工作要完成。他每天只能做一件工作。並且他知道這些工作分別要幾個工作天才能完成。另外，他也知道每個工作被延誤一天所需被罰的罰金。延誤的天數為從今天算起到該工作開始的那天 (所以只有第一件工作沒有罰金)。
以第一組測試資料為例說明：若工作的順序是 1 2 3 4，那罰金為：0×4 + 1000×3 + 4×2 + 6×5 = 3038。若工作的順序是 2 1 3 4，則罰金為：0×1000 + 1×4 + 4×2 + 6×5 = 42。所以第二種工作順序的罰金較少 (事實上也是最少)。
你的任務是寫一個程式幫助鞋匠找出完成這 𝑁 個工作的先後順序，使得罰金最少。
輸入的第一列有一個整數代表以下有幾組測試資料。
每組測試資料的第一列，含有一個整數 𝑁（1 ≤ 𝑁 ≤1000），代表鞋匠需完成的工作數。接下來的 𝑁 列每列有 2 個整數，分別代表該工作完成所需的天數以及延遲一天的罰金多少 (均大於等於 1，小於等於 1000)。
第一列和第一組測試資料間，以及各組測試資料間均有一空白列。請參考範例輸入。
對每組測試資料輸出一列，為這 𝑁 個工作的順序使得罰金最少。工作之間以一空白字元分隔。如果有不只一組答案，請輸出字典順序最小的那組。
各組測試資料間亦請輸出一空白列。請參考範例輸出。
2 4 3 4 1 1000 2 2 5 5 5 3 4 1 1000 8 8 2 2 5 6
2 1 3 4 2 1 5 3 4
Lucky貓 ★★★ 中 英