有 n 位同學同時找老師答疑。每位同學都預先估計了自己答疑的時間。老師可以安排答疑的順序，同學們要依次進入老師辦公室答疑。 一位同學答疑的過程如下： 首先進入辦公室，編號為 i 的同學需要 s i 毫秒的時間。然后同學問問題老師解答，編號為 i 的同學需要 a i 毫秒的時間。 答疑完成后，同學很高興，會在課程群里面發(fā)一條消息，需要的時間可以忽略。最后同學收拾東西離開辦公室，需要 e i 毫秒的時間。一般需要 10 秒、20 秒或 30 秒，即 e i 取值為 10000，20000 或 30000。一位同學離開辦公室后，緊接著下一位同學就可以進入辦公室了。答疑從 0 時刻開始。老師想合理的安排答疑的順序，使得同學們在課程群里面發(fā)消息的時刻之和最小。
輸入
輸入第一行包含一個整數(shù) n，表示同學的數(shù)量。 接下來 n 行，描述每位同學的時間。其中第 i 行包含三個整數(shù) s i , a i , e i ，意 義如上所述。
【樣例說明】 按照 1, 3, 2 的順序答疑，發(fā)消息的時間分別是 20000, 80000, 180000。 【評測用例規(guī)模與約定】 對于 30% 的評測用例，1 ≤ n ≤ 20。 對于 60% 的評測用例，1 ≤ n ≤ 200。 對于所有評測用例，1 ≤ n ≤ 1000，1 ≤ s i ≤ 60000，1 ≤ a i ≤ 1000000，e i ∈ {10000,20000,30000}，即 e i 一定是 10000、20000、30000 之一