30683번 - 별이 빛나는 밤 (Hard)

문제

본 문제와 Easy 문제는 입력 제한만 다른 동일한 문제이다.

스타는 밖에서 밤하늘 사진을 찍고 있다. 이 중 가장 잘 찍힌 사진을 액자에 담아 전시하려고 한다. 가장 잘 찍은 사진을 어떻게 고를지 고민하던 스타는 다음과 같은 방법으로 각 사진에 점수를 매기려고 한다.

그 당시 밤하늘을 2차원 격자로 나타낼 수 있으며 각 칸은 $(x, y)$로 표현한다. 그리고 스타가 찍은 사진에 담긴 밤하늘의 영역은 항상 직사각형이며 격자 칸 일부만 사진에 포함되는 경우는 없다.

별 $N$개에 대하여 각 별의 위치를 $(x_i, y_i),ドル 밝기를 $p_i$라고 하면 격자 칸 $(x, y)$에서의 밝기 $b_{x, y}$는 다음과 같이 계산한다.

$b_{x, y} = \sum_{i = 1}^N max(p_i-(|x-x_i|+|y-y_i|), 0)$

마지막으로 사진에 담긴 밤하늘의 격자 중 맨 왼쪽 아래가 $(a, b),ドル 맨 오른쪽 위가 $(c, d)$일 때, 사진의 점수 $score$는 다음과 같이 계산한다.

$score=\sum_{y = b}^d \sum_{x = a}^c b_{x, y}$

사진과 사진을 찍을 당시 밤하늘에 떠 있던 별 $N$개에 대한 정보가 주어졌을 때, 사진의 점수를 구해보자.

입력

첫째 줄에 별의 개수 $N$이 주어진다. $(1 \leq N \leq 500 ,円 000)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 별의 위치 $x_i, y_i$와 밝기 $p_i$가 주어진다. 두 개 이상의 별이 같은 위치에 있는 경우는 없다. $(-10 ,円 000 \leq x_i \leq 10 ,円 000;$ $-10 ,円 000 \leq y_i \leq 10 ,円 000;$ 1ドル \leq p_i \leq 10 ,円 000)$

마지막 줄에는 사진에 대한 정보 $a, b, c, d$가 주어진다. 이는 사진에 담긴 밤하늘의 격자 중 맨 왼쪽 아래에 있는 격자가 $(a, b),ドル 맨 오른쪽 위에 있는 격자가 $(c, d)$라는 것을 의미한다. $(-10 ,円 000 \leq a \leq c \leq 10 ,円 000;$ $-10 ,円 000 \leq b \leq d \leq 10 ,円 000;$ $c-a \leq 10 ,円 000;$ $d-b \leq 10 ,円 000)$

입력으로 주어지는 모든 수는 정수이다.

출력

사진의 점수를 출력한다.

제한

힌트