Problem C
Boris

På tågen i Philips hemstad brukar man kunna hitta världens finaste reklamskylt. Denna skylt har en bild på ingen mindre än matteläraren Boris, tillsammans med texten "Räkna med Boris". Naturligtvis har Philip blivit helt besatt av att samla på dessa fina reklamskyltar, och nu behöver han din hjälp med att optimera sin rutt mellan tågstationerna i staden för att få tag på så många Borisar som möjligt.

Genom sitt breda kontaktnät har Philip fått veta att i den närmaste framtiden kommer $N$ tåg att avgå från staden. För varje tåg vet han avgångstiden räknat i sekunder efter starten av hans jakt, antalet Borisar som kommer finnas på tåget samt koordinaterna för tågstationen, angett i meter. För att kunna ta Borisarna på tåget måste han som senast vara på plats exakt den sekunden som tåget ska gå, men om han vill kan han ju också komma dit i förväg och vänta på tåget i lugn och ro. Eftersom Philip älskar Boris så pass mycket, och inte heller vill råka fastna på ett tåg som kommer föra bort honom från sin hemstad, är han supersnabb med att plocka upp alla Borisar på tåget och grejar det på 0 sekunder. Notera att oavsett hur lång tid i förväg han kommer fram kan han ändå inte ta Borisarna innan tågets avgångstid, för det är först då som dörrarna in till tåget öppnas.

I sådana stressiga situationer som att jaga efter Borisar blir det väldigt påfrestande för Philip att hålla någon noggrannare koll på väderstrecken. För att inte riskera att gå vilse vill han därför bara röra sig rakt norrut, söderut, österut eller västerut, så att han lättare vet vart han är på väg.

Eftersom Philip har gott om tid till att förbereda sitt äventyr kan han börja vart som helst i staden. När han sedan börjar rör han sig med hastigheten 1 meter/sekund. Philip har en väldigt stor ryggsäck, så han kan bära hur många Borisar som helst på en gång.

Vad är det största antalet Borisar som Philip kan samla på sig?

Indata

Den första raden inehåller ett heltal $N$ ($1 \le N \le 2\, 000$), antalet tåg.

Därefter följer en rad per tåg. Varje rad innehåller fyra heltal: avgångstiden $t$ i sekunder efter start ($0 \le t \le 5 \cdot 10^8$), antalet Borisar $s$ på tåget ($1 \le s \le 500\, 000$), samt koordinaterna $x, y$ på den station tåget avgår från ($0 \le x, y \le 5 \cdot 10^8$).

Inga två tåg kommer avgå samtidigt från exakt samma station.

Utdata

Skriv ut en rad med ett heltal – det största antalet Borisar som Philip kan samla på sig.

Poängsättning

Din lösning kommer att testas på ett antal testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Notera att vissa exempelfall är inte giltiga i vissa testfallsgrupper.

Förklaring av exempelfall

I det tredje exempelfallet finns det fyra avgångar. Vi kallar dessa för tåg $0$ - tåg $3$, i den ordning de visas i indatan.

Om Philip börjar i punkten $(493,377)$ kan han ta $952$ Borisar från tåg $3$ vid tiden $148$. Sedan har han exakt $164$ meter att gå (vilket tar $164$ sekunder) till tåg $1$. Det har avgångstid $312$, d.v.s. $164$ sekunder efter tåg $3$. Han hinner alltså precis till tåg $1$ och kan ta dess $911$ Borisar. Därifrån hinner han, med $6$ sekunders marginal, gå till tåg $2$ och ta $927$ Borisar därifrån. Totalt får han alltså $952+911+927=2790$ Borisar.

2
10 1 0 0
10 1 1 1

1

2
10 1 0 0
12 1 1 1

2

4
332 357 378 891
312 911 650 384
431 927 758 379
148 952 493 377

2790