8. Astrálne kamene

Bola už hlboká noc, keď sa Jožko prebudil zo spánku. Sníval sa mu veľmi živý sen, z oblohy padali asteroidy, plné prerôznych krásnych kameňov¹. Nadšený, úplne zabudol, že to bol iba sen, vyskočil z postele a vybehol von. Nočná obloha bola jasná, hviezdy svietili… a, čo to? Zreteľne padala hviezda. Jožko, ešte v papučiach, sa za ňou rozbehol, keď sa v tej tme potkol a spadol. Pozrel sa na zem a, čo nevidí? Kameň! To nemôže byť náhoda. Ako sa zahľadel zas na oblohu všimol si ďalší, zreteľne padajúci asteroid. Už nečakal a rozbehol sa za ním. V svetle mesiaca uvidel dopadnutý kameň, ešte krajší ako predchádzajúci, ale ako sa poň načahoval, rozplynul sa mu pred očami.

Zvláštne, pomyslel si Jožko. Skúšal zabehnúť ešte za pár kameňmi, ale polovicu nestihol, rozplynuli sa. Keďže je Jožko zvedavý chlapec, hneď sa rozhodol vyskúmať, ako to je s tými kameňmi. Napriek tomu, že bola hlboká noc, hackol sa do satelitných dát a vypočítal kedy, kde a aký² kameň dopadne. Ostávajú posledné hodiny noci a Jožko sa zas vyberá na lov kameňov. Zaujímalo by ho, s akým úlovkom vie skončiť.

Úloha

Svet si vieme predstaviť ako priamku.

Na zem postupne spadne \(n\) (\(n \leq 500\,000\)) kameňov, \(i\)-tý z nich v čase \(t_i\), na mieste \(x_i\) a má hodnotu \(v_i\). Dva kamene môžu spadnúť na rovnaké miesto, alebo v rovnakom čase (nie však obe naraz). Pre jednoduchosť všetky časy sú v celých sekundách a súradnice v celých metroch. Kamene ostanú na mieste presne sekundu a potom sa rozplynú.

Jožko vie bežať jeden meter za sekundu. Na začiatku (v čase nula) stojí na súradnici \(p\). V prípade, že bude zbierať kamene optimálne, aký najväčší súčet hodnôt, ktorý vie získať?

Formát vstupu

Na prvom riadku sú dve medzerami oddelené čísla: \(n\), počet kameňov a \(p\), Jožkovú začiatočnú pozíciu.

V druhom riadku je \(n\) medzerami oddelených čísiel, \(t_1\) až \(t_n\), časy dopadu jednotlivých kameňov.

V treťom riadku je \(n\) medzerami oddelených čísiel, \(x_1\) až \(x_n\), miesta dopadu jednotlivých kameňov.

A na štvrtom riadku je \(n\) medzerami oddelených čísiel, \(v_1\) až \(v_n\) - hodnoty jednotlivých kameňov.

Je zaručené že dva kamene nedopadnú na rovnaké miesto v rovnaký čas.

Formát výstupu

Vypíšte dva riadky: na prvom, dve medzerami oddelené čísla - počet kameňov, ktoré Jožko v optimálnom prípade pozbiera a súčet ich hodnôt.

Na druhom riadku vypíšte čísla kameňov (číslo kameňa je jeho pozícia vo vstupe, číslované od nuly) ktoré má Jožko pozbierať, oddelené medzerou.

Ak existuje viac riešení, vypíšte ľubovoľné z nich.

Hodnotenie

Vaše programy budeme testovať na štyroch skupinách testovacích vstupov. Pre jednotlivé skupiny budú platiť nasledujúce obmedzenia:

Vo všetkých vstupoch, \(0 < v_i \leq 10^9\)

Príklad

Input:

3 0
60 40 50
0 35 40
3 1 1

Output:

1 3
0

Input:

6 3
7 3 5 3 4 8
10 0 2 4 5 4
20 3 9 5 7 8

Output:

3 22
2 5 3

Jožkovi sa oplatí najskôr vziať kameň, ktorý spadne v tretej sekunde na mieste jedna, potom prebehnúť na doľava na kameň s hodnotou 9. Napokon sa prejde dva metre doprava a zoberie kameň s hodnotou 8. Takto získa kamene s hodnotou 22. Ak by sa rozhodol zobrať kameň s hodnotou 20, potom nevie zobrať iný kameň.

Input:

3 0
0 1 2
1 2 3
100 100 100

Output:

0 0

Jožko žiaľ nestihne dobehnúť pre žiadny z kameňov.