루미 알고리즘

#1541골드Boris

PO 2022 온라인 예선코딩출제 Gustav Nilsson Gisleskog영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

In Philip's hometown, you can often find the world's most beautiful billboard. This billboard features none other than the math teacher Boris, along with the text “Count on Boris”. Naturally, Philip has become completely obsessed with collecting these beautiful billboards, and now he needs your help to optimize his route between train stations in the city to collect as many Borises as possible.

Through his extensive network, Philip has learned that in the near future, N trains will depart from the city. For each train, he knows the departure time in seconds after the start of his pursuit, the number of Borises that will be on the train, and the coordinates of the train station, given in meters. To collect the Borises on a train, he must be at the station exactly at the time the train departs, but he can also arrive early and wait for the train calmly if he wishes. Since Philip loves Boris so much and does not want to get stuck on a train that will take him away from his hometown, he is extremely quick at picking up all the Borises on the train and does it in 0 seconds. Note that no matter how early he arrives, he cannot collect the Borises before the train's departure time, as it is only then that the train doors open.

In such stressful situations as chasing Borises, it becomes very taxing for Philip to keep track of directions accurately. To avoid getting lost, he prefers to move only directly north, south, east, or west, so he knows more easily where he is headed.

Since Philip has plenty of time to prepare for his adventure, he can start anywhere in the city. Once he starts, he moves at a speed of 1 meter/second. Philip has a very large backpack, so he can carry as many Borises as he wants at once.

What is the maximum number of Borises that Philip can collect?

Input

The first line contains an integer N (1 ≤ N ≤ 2,000), the number of trains.

Following this are N lines, each describing one train. Each line contains four integers: the departure time t in seconds after the start (0 ≤ t ≤ 5 · 10^8), the number of Borises s on the train (1 ≤ s ≤ 500,000), and the coordinates x, y of the station from which the train departs (0 ≤ x, y ≤ 5 · 10^8).

No two trains will depart at the same time from exactly the same station.

Output

Output a single line with an integer – the maximum number of Borises that Philip can collect.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
18N ≤ 2
231N ≤ 16
333t, x, y ≤ 50 and s = 1.
428No additional constraints.

Explanation of Sample Case 3

In the third example case, there are four departures. We refer to these as trains 0 - train 3, in the order they appear in the input.

If Philip starts at the point (493,377), he can collect 952 Borises from train 3 at time 148. He then has exactly 164 meters to walk (which takes 164 seconds) to reach train 1. This train departs at 312, which is 164 seconds after train 3. So he arrives exactly in time for train 1 and can collect its 911 Borises. From there, he has 6 seconds to walk to train 2 and collect 927 Borises. In total, he can collect 952 + 911 + 927 = 2790 Borises.

예제

예제 1

입력
2
10 1 0 0
10 1 1 1
출력
1

예제 2

입력
2
10 1 0 0
12 1 1 1
출력
2

예제 3

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

출처 표기

출처: Programmeringsolympiaden 2022년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.