24191번 - 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?

입력

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.

출력

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

제한

힌트

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.