Секретний бункер йде на \(N\) поверхів униз. Під нижнім поверхом бункера знаходиться надсекретна лабораторія. Злісний диверсант хоче вивести лабораторію з ладу, заливши її водою (навіть дуже невеликої кількості води вистачить, щоб запоганити надточні прилади).

Для цього він використовує калюжі води, що залишаються від життєдіяльності мешканців бункера. У калюжках \(i\)-го поверху знаходиться \(E_i\) води. Диверсанту відомо, що якщо на ньому накопиться більше \(С_i\) води, то перегородка не витримає і вся вода зіллється на поверх нижче. Він може проробити отвори в деяких перегородках, якими вода також стече вниз. Виконати отвір у підлозі \(i\)-го поверху варто \(P_i\) у.о.

Допоможіть диверсанту знищити лабораторію із мінімальними матеріальними витратами.

Формат вхідних даних

Перший рядок вхідного файлу містить натуральне число \(N\) (\(1 ≤ N ≤ 500000\)) - кількість поверхів у бункері.

У наступних \(N\) рядках знаходяться трійки цілих чисел \(C_i, E_i, P_i\) (\(0 < E_i ≤ C_i < 1000000;\) \(E_1+E_2+...+E_N < 2000000000;\) \(P_i > 0;\) \(P_1+P_2+...+P_N < 2000000000\)). Поверхи нумеруються зверху донизу.

Формат вихідних даних

У першому рядку вихідного файлу вивести кількість грошей, які доведеться витратити злісному диверсанту.

В наступних рядках виведіть номери поверхів, в підлозі яких слід зробити отвори.

Приклад вхідних даних

4 
1 1 1 
1 1 3 
3 1 2 
3 1 10

Приклад вихідних даних

3
1
3