Все, кто играли в Cut the Rope, хорошо знают, как организовано прохождение игры. В игре все уровни разделены на коробки. Изначально доступна только одна коробка с несколькими уровнями. За прохождение уровней игрок зарабатывает звезды, по мере накопления звезд открываются новые уровни.
Представьте, что вы впервые играете в Cut the Rope. В данный момент вам доступны только уровни из первой коробки (кстати, она называется «Cardboard Box»). Каждый уровень характеризуется двумя целыми числами: ai — сколько требуется времени, чтобы пройти уровень на одну звезду, bi — сколько требуется времени, чтобы пройти уровень на две звезды (ai < bi).
Вы хотите как можно быстрее открыть следующую коробку с уровнями, для чего требуется заработать как минимум w звезд. Каким образом нужно действовать, чтобы это сделать? Обратите внимание, что проходить уровень можно только один раз: либо на одну звезду, либо на две. Необязательно проходить все уровни.
Выходные данные
В первой строке выведите целое число t — минимальное время, которое требуется, чтобы открыть следующую коробку.
В следующей строке выведите n цифр без пробелов — описание оптимального плана действий:
- если i-й уровень нужно пройти на одну звезду, i-я цифра должна быть равна 1;
- если i-й уровень нужно пройти на две звезды, i-я цифра должна быть равна 2;
- если i-й уровень вовсе не нужно проходить, i-я цифра должна быть равна 0.