Magishow

Magikern Mårten håller just nu på att uppträda i en magnifik magitävling. Tävlingen består av $N$ rundor. I varje runda använder Mårten sin magi för att göra ett av två trick: antingen trollar han fram $x$ kaniner, eller så saboterar han ett av sina motståndares trick genom att trolla bort $y$ av deras kaniner. Han kan också välja att inte göra något.

För varje kanin som Mårten trollar fram eller trolla bort måste han använda 1 magi. I början av showen har han $K$ magi. När han har slut på magi så kan han inte längre utföra trick.

Poängsättningen i tävlingen är enkel. I runda $i$, låt

I runda $i$, om $S_ i$ är i intervallet $[L[i], R[i]]$ där $L[i]$ och $R[i]$ är heltal specifika till runda $i$, så får han $|S_ i - \frac{L[i] + R[i]}{2}|$. Om $S_ i$ är utanför intervallet får han istället $0$ poäng. Notera att Mårten endast kan utföra sin magi på hela kaniner, så $S_ i$ kommer alltid att vara ett heltal.

Mårtens totala poäng i tävlingen är summan av hans poäng för varje runda. Vad är den maximala poängen Mårten kan uppnå?

Exempel

Betrakta en tävling med $N = 4$ rundor, där Mårten har $K = 5$ magi i början av tävlingen. Intervallen för rundorna är $[3, 5]$ för första rundan, $[-2, 2]$ för andra rundan, $[-2, 0]$ för tredje rundan, och $[2, 6]$ för sista rundan.

Mårtens optimala trick är då att i första rundan inte göra något ($0$ poäng), trolla bort två kaniner i andra rundan ($|-2 - 0 | = 2$ poäng), inte göra något i tredje rundan ($|0 - (-1)| = 1$ poäng) och trolla fram 2 kaniner i sista rundan ($|2 - 4| = 2$ poäng).

Totalt blir detta $0 + 2 + 1 + 2 = 5$ poäng, vilket är den bästa möjliga poängen. Notera att det finns flera optimala strategier i detta exempel. Totalt använde han $0 + 2 + 0 + 2 = 4$ magi, så Mårten har en magi över efter sista rundan.

Uppgift

Givet alla rundorna i tävlingen, bestäm den maximala poängen Mårten kan få, och ge honom instruktioner för hur han uppnår den.

Du ska implementera funktionen magic_score(N, K, L, R).

• magic_score(N, K, L, R) - denna funktion anropas exakt en gång av domaren.

  • N: antalet rundor i tävlingen.

  • K: mängden magi Mårten har i början av tävlingen.

  • L: en vektor med $N$ element, som innehåller värdena L[i] som beskrivs i uppgiften.

  • R: en vektor med $N$ element, som innehåller värdena R[i] som beskrivs i uppgiften.

  • $-1\, 000\, 000 \le L[i] \le R[i] \le 1\, 000\, 000$

  • $L[i] + R[i]$ är jämnt

  • Funktionen ska returnera den maximala poäng som Mårten kan få.

Du ska dessutom anropa funktionen trick(X) för att berätta för Mårten vad han ska göra i varje runda.

• trick(X) - denna funktion ska anropas en gång per runda av ditt program. Det $i$:te anropet ska ge instruktionen till Mårten för den $i$:te rundan, om han ska spela optimalt.

  • X: denna parameter ska ge värdet $S_ i$ på varje av Mårtens rundor. Om Mårten ska trolla fram kaniner, så ska detta värde vara antalet kaniner Mårten ska lägga till. Om han ska trolla bort kaniner ska detta vara minus antalet kaniner Mårten trollade bort. Om han inte ska utföra något trick ska värdet vara $0$.

  • Funktionen har inget returvärde.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/magic.zip.

Delpoäng

Uppgiften består av ett antal grupper. Varje grupp ger ett visst antal poäng, och för att klara gruppen måste du klara samtliga testfall i gruppen.

För varje delgrupp, om du svarar rätt returvärde på magic_score(N, K, L, R) är rätt men dina anrop till trick(X) inte är en giltig sekvens som ger maximal poäng, så får du $75\% $ av gruppens poäng. Detta kommer synas som Partially correct on de testfall där så är fallet. Notera att du alltid måste göra $N$ anrop till trick(X), även om sekvensen inte är korrekt.

Indataformat

Exempeldomaren läser indata i följande format:

• rad $1$: N K

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

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

Utdataformat

Exempeldomaren skriver utdata på följande format:

• rad $1$: returvärdet av magic_score(N, K, L, R)

• rad $2$: $N$ heltal, värdena som ges av anropen till trick(X) i ordning.

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

5
0 2 0 2