Problem C
Magic Show

Mårten the Magician is currently performing in a magnificent magic competition. The show consists of $N$ rounds. In each round, Mårten uses his magic to perform one of two tricks: either he makes some number $x$ rabbits appear, or he sabotages his opponents’ tricks by making some number $y$ of their rabbits disappear. He can also choose to do neither.

For each rabbit Mårten makes appear or disappear, he must use 1 magick. In the beginning of the show, Mårten has $K$ magicks. When he has run out of magicks, he can no longer perform a trick.

The scoring of the competition is easy. In the $i$:th round, let

In round $i$, if $S_i$ is in the interval $[L[i],R[i]]$ where $L[i]$ and $R[i]$ are integers specific to the round, he gets $|S_i-\frac{L[i]+R[i]}{2}|$ points. If $S_i$ is outside this interval, Mårten gets $0$ points. Note that Mårten cannot perform his magic on fractional rabbits, thus $S_i$ will always be an integer.

Mårten’s total score in the competition is the sum of scores among all the rounds. What is the maximum score Mårten can get if he performs optimally?

Example

Consider a competition with $N=4$ rounds, where Mårten has $K=5$ magicks at the start of the show. The round intervals are $[3,5]$ for the first round, $[-2,2]$ for the second round, $[-2,0]$ for the third round, and $[2,6]$ for the last round.

The optimal play from Mårten is then to do nothing in the first round ($0$ points), remove two rabbits in the second ($|-2-0|=2$ points), do nothing in the third round ($|0-(-1)|=1$ point), and create 2 rabbits in the last round ($|2-4|=2$ points).

This totals $0+2+1+2=5$ points, which is the best possible score. Note that there are several optimal strategies in the example. In total, he used $0+2+0+2=4$ magicks, leaving an unused magick after the last round.

Task

Given all the rounds of the competition, you are to determine the maximum score Mårten can get, and construct instructions for him.

You should implement the function magic_score(N, K, L, R).

• magic_score(N, K, L, R) - this function will be called exactly once by the judge.

  • N: the number of rounds in the competition.

  • K: the amount of magicks Mårten has in the beginning of the show.

  • L: an array with $N$ elements, containing the values L[i] as descriped in the task.

  • R: an array with $N$ elements, containing the values R[i] as descriped in the task.

  • $-1000000\le L[i]\le R[i]\le 1000000$

  • $L[i]+R[i]$ is even

  • The function should return the maximum score Mårten can obtain.

Additionally, you should call the function trick(X) to tell Mårten what he should do in each round.

• trick(X) - this function should be called by your program once for every round. The $i$:th call should give the instruction to Mårten in the $i$:th round if Mårten wants to play optimally.

  • X: this parameter should give the value $S_i$ of each of Mårten’s rounds. If Mårten should add rabbits, this value should be the number of rabbits Mårten should add. If he should remove rabbits, it should be the negative value of the number of rabbits he removes. If he should not do any trick in the round, the value should be $0$.

  • The function has no return value.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/magic.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

For each subtask, if the return value of magic_score(N, K, L, R) is correct, but your calls to trick(X) is not a valid sequence giving the maximum score, you will get $75\mathrm{\%}$ of the score of the subtask. This will show up as Partially correct on these test cases. Note that you always must make exactly $N$ calls to trick(X), even if the sequence is incorrect.

Input format

The sample judge reads input in the following format:

• line $1$: N K

• line $2$: L[0] L[1] .. L[N - 1]

• line $3$: R[0] R[1] .. R[N - 1]

Output format

The sample judge writes output in the following format:

• line $1$: the return value of magic_score(N, K, L, R) on a line

• line $2$: $N$ integers, the values given from the calls to trick(X) in order.

4 5
3 -2 -2 2
5 2 0 6

5
0 2 0 2