Cards#1867
On his birthday, Vasya gave his brother Petya a set of cards. Then Vasya and Petya each wrote a number on every card: Vasya on one side, and Petya on the other. Afterwards, the brothers scattered the cards around the room and ran away. Their grandmother, Lyudmila Petrovna, saw the mess. She had worked for many years as an accountant, so she decided to reminisce and invent a game for herself: she could turn some cards with the "Vasya" side up and others with the "Petya" side up, in such a way that the total sum on the visible sides is as large as possible. However, because she loves both brothers equally, she added an extra condition: the number of cards turned "Petya" side up should differ from the number turned "Vasya" side up by no more than .
Lyudmila Petrovna easily solved the problem, but can you?
The first line contains the numbers and (1 \leq N \leq 100\ 000, 1 \leq K \leq N) — the number of cards and the maximum allowed difference. Each of the next lines describes a card — two integers: the first number is written by Vasya on one side, and the second number by Petya on the other side. The absolute value of each number does not exceed 10^9.
The first line should contain a single number — the maximum possible sum. Then output numbers: for each card, output 1 if its Petya side is up, and 0 if its Vasya side is up.
If there are multiple answers, output any of them.
Example 1