Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Cardboard Box

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEveryone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: *a*_{i} — how long it takes to complete the level for one star, *b*_{i} — how long it takes to complete the level for two stars (*a*_{i} < *b*_{i}).

You want to open the next box as quickly as possible. So, you need to earn at least *w* stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

Input

The first line contains two integers *n* and *w* (1 ≤ *n* ≤ 3·10^{5}; 1 ≤ *w* ≤ 2*n*) — the number of levels in the first box and the number of stars you need to open another box. Each of the following *n* lines contains two integers *a*_{i} and *b*_{i} (1 ≤ *a*_{i} < *b*_{i} ≤ 10^{9}) — the attributes of the *i*-th level.

Output

In the first line print integer *t* — the minimum time you need to open the next box.

In the next line, print *n* digits without spaces — the description of the optimal scenario:

- if you need to pass the
*i*-th level for one star, the*i*-th digit should equal 1; - if you need to pass the
*i*-th level for two stars, the*i*-th digit should equal 2; - if you do not need to pass the
*i*-th level at all, the*i*-th digit should equal 0.

Examples

Input

2 3

1 2

1 2

Output

3

12

Input

5 3

10 20

5 10

10 20

6 9

25 30

Output

14

01020

Note

In the first test sample, answer 21 is also assumed correct.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2017 10:24:11 (c3).

Desktop version, switch to mobile version.
User lists

Name |
---|