| Zepto Code Rush 2014 |
|---|
| Закончено |
Все, кто играли в Cut the Rope, хорошо знают, как организовано прохождение игры. В игре все уровни разделены на коробки. Изначально доступна только одна коробка с несколькими уровнями. За прохождение уровней игрок зарабатывает звезды, по мере накопления звезд открываются новые уровни.
Представьте, что вы впервые играете в Cut the Rope. В данный момент вам доступны только уровни из первой коробки (кстати, она называется «Cardboard Box»). Каждый уровень характеризуется двумя целыми числами: ai — сколько требуется времени, чтобы пройти уровень на одну звезду, bi — сколько требуется времени, чтобы пройти уровень на две звезды (ai < bi).
Вы хотите как можно быстрее открыть следующую коробку с уровнями, для чего требуется заработать как минимум w звезд. Каким образом нужно действовать, чтобы это сделать? Обратите внимание, что проходить уровень можно только один раз: либо на одну звезду, либо на две. Необязательно проходить все уровни.
В первой строке записаны два целых числа n и w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — количество уровней в первой коробке и количество звезд, которое требуется, чтобы открыть следующую коробку. В каждой из следующих n строк записаны два целых числа ai и bi (1 ≤ ai < bi ≤ 109) — характеристики i-го уровня.
В первой строке выведите целое число t — минимальное время, которое требуется, чтобы открыть следующую коробку.
В следующей строке выведите n цифр без пробелов — описание оптимального плана действий:
- если i-й уровень нужно пройти на одну звезду, i-я цифра должна быть равна 1;
- если i-й уровень нужно пройти на две звезды, i-я цифра должна быть равна 2;
- если i-й уровень вовсе не нужно проходить, i-я цифра должна быть равна 0.
2 3
1 2
1 2
3
12
5 3
10 20
5 10
10 20
6 9
25 30
14
01020
В первом тестовом примере ответ 21 также считается правильным.
