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