Лёша любит программирование и олимпиады и поэтому достаточно часто пишет раунды на сайте Codeforces. Однако за многие годы он так и не получил красный цвет. Тому есть целый ряд причин: иногда происходит перерасчёт рейтинга, иногда Лёша поздно приходит на работу и уже не успевает вернуться домой к раунду, а иногда он просто уклоняется от раундов китайских авторов, поскольку считает, что они плохого качества.

Но сегодня не такой день, сегодня всё складывается очень хорошо: раунд не китайский, Лёша пришёл на работу вовремя, и, главное, он каким-то образом узнал темы задач и разбалловку!

В раунде будет n задач. Изначально i-я задача оценивается в a_i баллов, однако каждую минуту её стоимость уменьшается на b_i баллов. Таким образом, если i-я задача была решена на минуте m_i от начала соревнований, участнику будет начислено за нее cost_i = a_i - b_i·m_i баллов. Леша решает все задачи подряд, и не тратит время на отдых. Он уверен, что независимо от того, какой порядок он выберет, на момент решения i-й задачи ее стоимость будет положительна.

Также для каждой задачи Лёша знает время t_i, в течение которого он напишет её решение: время решения задачи Лёшей зависит исключительно от того, на какую тему эта задача, а темы, как мы помним, он выяснил.

Конечно, Лёша хочет набрать максимально возможное количество баллов. Он догадывается, что количество набранных баллов зависит от порядка решения задач. Но сейчас он на работе и не хочет опоздать на раунд, так что вопрос определения порядка задач, обеспечивающего максимально возможное количество баллов, перекладывается на вас.