시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB119483433.663%

문제

DGIST의 밤하늘에는 $N$개의 별이 떠 있습니다. DGIST의 위치가 무한히 넓은 2차원 좌표계 위의 원점 $(0, 0)$이라고 하면, 별들이 떠 있는 위치는 $(X_i, Y_i)$로 나타낼 수 있습니다. 모든 별들이 떠 있는 위치는 서로 다르고, 원점 위에 떠 있는 별은 없습니다.

동현이는 밤하늘에 떠 있는 아름다운 별들의 사진을 찍어서 천체 사진 공모전에 참가하려고 합니다. 별의 사진을 찍으려면 망원경이 필요하기 때문에, 동현이는 우선 망원경부터 주문하기로 했습니다. 주문할 수 있는 망원경의 종류는 $M$ 가지가 있고, 각 망원경의 가격은 $P_i$ 입니다. 망원경의 가격이 비쌀수록 관측 성능이 올라갑니다. 가격이 $P_i$ 인 망원경으로는 관측 위치로부터 유클리드 거리의 제곱이 $P_i$ 보다 작거나 같은 곳에 위치한 별들을 관측할 수 있습니다. 

별들은 저마다 아름다움 수치 $S_i$ 를 가지고 있고, 어떤 사진의 아름다움은 그 사진에 찍힌 모든 별들의 아름다움 수치의 합으로 정의합니다. 그리고 가격이 $P_i$ 인 망원경으로 한 번에 사진에 담을 수 있는 별들의 영역은 원점을 꼭짓점으로 하고 중심각이 90도, 반지름의 길이가 $\sqrt{P_i}$ 인 부채꼴 모양으로 나타낼 수 있습니다.

동현이는 원하는 망원경을 하나 산 뒤, 최고로 아름다운 사진을 한 장 찍어서 공모전에 제출하려 합니다. 동현이는 공모전에서 입상도 하고 싶지만, 그렇다고 비싼 망원경을 구매하는 데 너무 많은 돈을 투자하고 싶지는 않습니다. 동현이를 위해 (사진의 아름다움) - (망원경의 가격)의 최댓값을 구해 줍시다.

입력

첫 번째 줄에는 별들의 개수를 의미하는 정수 $N$과 살 수 있는 망원경의 종류의 수 $M$이 공백으로 구분되어 주어집니다. $( 1 \le N \le 10^5,\  1 \le M \le 200 )$

두 번째 줄부터 $N + 1$ 번째 줄에는 별의 좌표 $X_i, Y_i$ 와 별의 아름다움 $S_i$ 가 공백으로 구분되어 주어집니다. $( -10^9 \le X_i, Y_i \le 10^9,\  0 \le S_i \le 10^{12},\  (X_i, Y_i) \neq (0, 0) )$ 

$N + 2$ 번째 줄에는 망원경의 가격 $P_1, P_2, P_3, ..., P_M$을 나타내는 정수 M개가 공백으로 구분되어 주어집니다. $(1 \le P_i \le 10^{18})$

출력

첫 번째 줄에 (사진의 가치) - (망원경의 가격)의 최댓값을 출력합니다.

예제 입력 1

8 2
0 2 6
2 2 8
2 0 3
2 -2 8
0 -2 7
-2 -2 1
-2 0 5
-2 2 5
4 8

예제 출력 1

11

예제 입력 2

5 3
6 2 89
-3 0 86
-4 0 98
5 1 60
10 -8 98
100 2 58

예제 출력 2

126

예제 입력 3

3 3
6 7 88
5 -2 62
-9 9 70
52 47 18

예제 출력 3

15

예제 입력 4

1 2
8 8 40
40 60

예제 출력 4

-40

출처

University > DGIST > 2022 DGIST 현풍전산배 알고리즘 대회 H번