Как и в обычном тетрисе, поле в игре Strategy Tetris представляет собой "стакан" шириной в W клеток (1<W<10
9) и бесконечной высоты. В этот стакан падают сверху N фигурок (1<N<100000). i-я фигурка представляет собой прямоугольник шириной в W
i клеток и высотой в одну клетку; самая левая клетка фигурки имеет абсциссу ai (1<a
i<W–W
i+1). Фигурки падают по обычным правилам: если при падении фигурка хотя бы одной своей клеткой ложится на какую-либо уже упавшую фигурку, то ее движение прекращается.
В отличие от обычного тетриса, игрок не имеет возможности вращать фигурки или смещать их по горизонтали в процессе падения — еще бы, это пришлось бы делать быстро и не было бы времени серьёзно подумать над стратегией. Единственное, что он может — это выбрать порядок, в котором эти N фигурок упадут в стакан (каждая по одному разу). Ваша задача — помочь ему выбрать такой порядок, при котором высота образовавшейся в результате падения конструкции была бы как можно меньше. (В отличие от обычного тетриса, полностью заполненная фигурками горизонталь никуда не исчезает).
На рисунке ниже приведен пример заполнения стакана фигурками из примера входных данных (порядок заполнения соответствует выходному файлу, приведенному в примере).
Входные данные
В первой строке записаны числа N и W, а в последующих N строках — пары чисел a
i и W
i.
Выходные данные
Выведите минимальную возможную высоту конструкции, а затем последовательность номеров фигурок, к этой высоте приводящую. Фигурки нумеруются натуральными числами от 1 до N в том порядке, в котором они указаны во входных данных. Если возможных вариантов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2
2 2
3 2
|
2
3 1 2
|