Размещение симбиотов (Basic)

시간 제한2초메모리 제한1024 MB

요약

2n개의 심비오트를 각 수용자가 최대 4개까지 담을 수 있고 위험도 합이 B 이하인 조건에서 배치하되, 각 쌍의 두 심비오트는 i번째나 i-1번째 수용자 쌍에서만 고르고 같은 수용자에 들어갈 수 없을 때, 필요한 최소 수용자 수와 배치를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 구현, 정렬
정답자: 아직 제출이 없습니다

문제

Вернемся немного во времени в события первого фильма, когда корпорация <<Фонд жизни>> проводила эксперименты на людях с участием симбиотов. В итоге все закончилось довольно хорошо, но давайте представим, что было бы, если Эдди с Веномом не остановили бы запуск ракеты, и еще больше симбиотов прибыли бы на Землю.

Прилетевшие $2n$ симбиотов хотят найти себе носителей, и для этого они отобрали $2n$ самых здоровых людей. Известно, что $i$ -й симбиот обладает опасностью $a\_i$ , а $i$ -й носитель --- вместимостью ровно $B$ . Отобранные люди оказались настолько крепкими, что каждый из них может вместить аж до четырех симбиотов одновременно, но только если их суммарная опасность не превышает вместимости носителя.

Чтобы все было честно, был определен следующий порядок объединения с носителями:

все носители разбиваются на пары, в паре номер $i$ находятся носители с номерами $2i - 1$ и $2i$ (нумерация как носителей, так и пар, с единицы);
аналогичным образом на пары разбиваются все симбиоты;
каждый симбиот из $i$ -й пары может выбрать произвольного носителя из $i$ -й или $(i - 1)$ -й пары (если, конечно, его вместимости для этого хватает).

При этом так случайно получилось, что симбиоты, находящиеся в одной паре, не очень любят друг друга, и отказываются находиться в одном носителе.

Помогите симбиотам определить, какого минимального числа носителей достаточно, чтобы вместить в себя всех симбиотов по описанным правилам. Остальные будут \sout{съедены} отпущены домой.

입력

В первой строке ввода через пробел даны два целых числа: $n$ --- количество пар симбиотов (и, соответственно, носителей), и $B$ --- вместимость каждого носителя ( $1 \leqslant n \leqslant 3 \cdot 10^5$ ; $1 \leqslant B \leqslant 10^9$ ).

Во второй строке через пробел перечислены $2n$ целых чисел $a\_i$ --- значения опасности каждого симбиота ( $1 \leqslant a\_i \leqslant B$ ).

출력

В первой строке вывода выведите минимальное количество носителей $t$ , которого хватит для размещения всех симбиотов с соблюдением всех описанных условий.

В следующей строке через пробел выведите $2n$ целых чисел $h\_i$ --- номера носителей, в которых должны расположиться симбиоты, на $i$ -м месте --- номер носителя для $i$ -го симбиота. Должно выполняться $h\_{2i - 1} \neq h\_{2i}$ для всех $i$ от $1$ до $n$ .

Если распределений симбиотов по носителям, приводящих к оптимальному ответу, несколько, выведите любой подходящий ответ.

예제2

예제 1
입력
```
2 8
4 5 6 7
```
예상 출력
```
4
1 2 3 4
```
예제 2
입력
```
2 8
3 4 5 6
```
예상 출력
```
3
1 2 1 4
```