Поликарп принимает участие в соревновании по программированию по инновационным правилам, которые называются TopoCM++. Участникам предлагается решить n задач, причем, время на их решение неограниченно. Для каждой задачи было заранее подсчитано ожидаемое время отправки решения, для i-й задачи ожидаемое время отправки решения равно ti.
В идеальном случае, участник должен отослать каждую задачу не позже, чем ее ожидаемое время отправки решения ti, но в реальном мире некоторые участники не укладываются в эти сроки. Так как соревнование длится бесконечное время, то рано или поздно каждый из участников решит все предложенные задачи, и поэтому очки участника зависят только от максимальной задержки по всем задачам. Цель каждого из участников — решить задачи в указанные времена. Если это невозможно, то необходимо минимизировать максимум из значений ri - ti, где ri — это время, когда i-ая задача фактически была решена (отправлено решение).
Поликарп внимательно изучил все задачи и подсчитал, что ему потребуется для i-й задачи ai единиц времени для придумывания решения и bi времени для того, чтобы его написать. Таким образом, общее время, необходимое для решения i-й задачи, равно ai + bi единиц времени.
К сожалению, Поликарп не умеет делать сразу несколько дел в одно и то же время, и поэтому он собирается организовать свою работу следующим образом. Всего он должен выполнить 2n дел: придумать n решений («работа головой») и затем написать их («работа на компьютере»). Поликарп может выполнять эти дела в произвольном порядке, но с одним условием: для каждой задачи, разумеется, необходимо сначала придумать решение, а только потом написать его. Кроме того, он не может прерывать начатое дело, то есть он обязан полностью завершить текущее дело перед тем, как взяться за следующее.
Каждый раз, когда Поликарп переключается между видами работ (с работы головой на работу на компьютере или обратно), ему требуется немного отдохнуть. Он знает значения ft и fc, где ft означает время, необходимое на отдых перед работой головой, и fc означает время, необходимое на отдых перед работой на компьютере. Кроме того, Поликарпу необходимо ft времени прежде чем приступить к самому первому делу (разумеется, это работа головой, так как прежде чем что-то писать, необходимо немного подумать).
Помогите Поликарпу найти такой порядок выполнения дел, чтобы минимизировать максимум из задержек по всем задачам.
В первой строке входных данных записаны три целых числа n, ft и fc (1 ≤ n, ft, fc ≤ 2·105). Следующие n строк содержат описания задач по одному описанию на строке, в i-й из этих строк записаны целые числа ai, bi и ti (1 ≤ ai, bi ≤ 2·105; 1 ≤ ti ≤ 1012), где ai означает время, необходимое для придумывания решения по i-й задаче, bi означает время, необходимое для того, чтобы написать решение, а ti означает ожидаемое время, когда решение по ней должно быть отослано.
В первую строку выведите минимальный максимум из задержек по всем задачам. Более формально, это число равно минимальному возможному значению величины max{ri - ti} по всем задачам, которые не были решены вовремя, где ri означает время, в которое Поликарп отослал решение по i-й задаче.
Во вторую строку выведите последовательность из 2n чисел. Для каждого i от 1 до n эта последовательность должна содержать ровно один раз число - i и ровно один раз число i, где - i означает придумывание решения по i-й задаче, а число i означает написание решения.
5 2 2
3 3 4
2 1 21
1 3 8
1 3 20
1 2 16
8
-4 -3 -1 1 3 -2 -5 5 2 4
