Informatica Online Judge

  마카롱 먹기 [1583 / 062F]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (14073 윤희헌)]

Background

미르는 마카롱을 먹는 것을 좋아한다. 마카롱을 먹을때마다 미르는 거리 1만큼 이동할 에너지를 얻는다.

미르가 집에서 학교까지 등교하는데 주변에 마카롱들이 많이 존재한다. 미르는 등하교길 주변의 마카롱중 몇개를 먹어서 학교에 도착했을때 최대의 에너지를 가지고자 한다.

이런 미르를 도와주자.

이때 거리는 맨해튼 거리를 사용한다. 즉 집이 (1,1)에 위치하고 학교가 (3,4)에 위치하면 집에서 학교까지 이동하는데 5의 에너지가 필요하다.

단, 학교와 집 그리고 마카롱들의 위치는 중복될 수 있다.

Input

첫번째 줄에 시작할때 가지고 있는 에너지 e가 주어진다. (0 ≤ e ≤ 40)

두번째 줄에 집의 위치의 x좌표 hx와 y좌표 hy가 주어진다. (0 ≤ hx, hy ≤ 50)

세번째 줄에 학교의 위치의 x좌표 sx와 y좌표 sy가 주어진다. (50 ≤ sx, sy ≤ 100)

네번째 줄에 마카롱이 있는 위치들의 수 n이 주어진다. (0 ≤ n)

이후 n개의 줄에 마카롱이 있는 위치 x좌표 mx와 y좌표 my, 그리고 그 위치에 존재하는 마카롱의 수 mn이 주어진다. (0 ≤ mx, my ≤ 100, 0 ≤ mn ≤ 40)

10개의 테스트케이스 중 5개는 n ≤ 25 이며, 나머지 5개는 n ≤ 100이다.

Output

학교에 도착했을 때 가지고 있을 수 있는 최대의 에너지를 출력한다. 만약 학교에 도착할 수 없다면 -1을 출력한다.

IO Example

입력1
10
1 1
3 3
1
2 2 2

출력1
8

입력2
10
1 1
3 3
5
2 2 2
12 21 8
3 4 7
30 30 1
40 40 2

출력2
13

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]