29065번 - Выбор оружия 스페셜 저지다국어

Победа уже близко, и Китнисс планирует последнее наступление. Нужно много людей и, конечно же, оружия. Оружие бывает двух типов: автоматическое (автоматы, пистолеты, пулеметы) и метательное (ножи, лук, арбалет). Каждый человек по-своему умеет обращаться с обоими типами оружий. Так, для каждого солдата Китнисс узнала два числа --- его эффективность обращения с автоматическим оружием и метательным соответственно. Теперь ей надо каждому человеку выдать ровно один тип оружия, причем понятно, что сделать она это хочет таким образом, чтобы суммарная эффективность обращения с оружием всех людей была максимальна. Однако, и отправлять в бой одних лучников или одних автоматчиков --- не лучшая идея. Поэтому Китнисс также решила, что количество людей, которым она даст метательное оружие и людей, которым она даст автоматическое оружие, будет отличаться не более чем на $m$.

В первой строке входного файла дано два числа $n$, $m$ ($1 \le n \le 100\,000, 1 \le m \le n$) --- количество солдат, готовых идти в бой, и максимальная разница количества людей, которые получат автоматическое оружие, и людей, которые получат метательное оружие соответственно.

В следующих $n$ строках заданы умения людей обращаться с оружием. $i+1$-я строка входного файла содержит два числа $a_i$, $b_i$ ($1 \le a_i, b_i \le 10\,000$) --- эффективность обращения $i$-го человека с автоматическим и метательным оружием соответственно.

В первой строке выходного файла выведите суммарную эффективность обращения с оружием все солдат. Во второй строке выведите $n$ чисел, $i$-е из которых равно 0 или 1 --- 0 означает, что солдату номер $i$ дали автоматическое оружие и 1, если метательное.

В первом тестовом примере оба солдата одинаково владеют метательным и автоматическим оружием. Однако, дать им обоим автоматическое оружие нельзя --- количество людей с автоматическим оружием и количество людей с метательным оружием должно отличаться не более чем на 1.

Во втором тестовом примере опять же нельзя дать всем трем солдатам автоматическое оружие, поэтому оптимальный вариант --- дать первым двум из них автоматическое, а третьему --- метательное, тогда суммарное умение будет равно $2+3+2=7$.