점심 콘서트

시간 제한1초메모리 제한1024 MB

요약

수직선 위에서 연주회 위치를 정수로 정할 때, N명의 친구가 각자의 청취 범위 안에 들어오기 위해 걷는 시간의 합을 최소로 만드는 값을 구한다.

난이도: 보통10점 중 7점
유형: 수학, 정렬, 그리디, 누적 합
정답자: 아직 제출이 없습니다

문제

학교에 점심시간이 찾아왔다! 늘 그렇듯 N명의 친구들이 긴 운동장에 서 있다. 운동장은 수직선으로 나타낼 수 있고, i번째 친구는 처음에 위치 $P_i$ 미터에 서 있다. i번째 친구는 운동장을 따라 양쪽 어느 방향으로든 $W_i$ 초에 1미터의 속도로 걸을 수 있으며, 청력이 좋아 자기 위치에서 $D_i$ 미터 이내(경계 포함)의 음악을 들을 수 있다. 여러 학생이 처음에도, 걸은 뒤에도 같은 위치에 있을 수 있다.

당신은 운동장의 어떤 위치 $c$ 미터에서 작은 콘서트를 열고 (c는 당신이 정하는 정수), 모든 친구에게 문자를 보낼 것이다. 그러면 각 친구는 콘서트를 들을 수 있게 되는 최소 시간 동안 걷는다. 다시 말해 각 친구 i는 $c$ 에서 $D_i$ 이내에 있게 된다.

모든 N명의 친구가 걸은 시간의 합을 최소화하는 $c$ 를 고르려고 한다. 이 최소 합은 몇 초인가? 결과가 32비트 정수 범위를 넘을 수 있음에 주의하자.

입력

첫째 줄에 N이 주어진다.

다음 N개의 줄에는 세 정수 $P_i$ , $W_i$ , $D_i$ 가 공백으로 구분되어 주어진다 ( $1 \le i \le N$ ).

다음 표는 주어진 15점이 어떻게 배분되는지 보여준다.

출력

모든 N명의 친구가 콘서트를 들을 수 있게 되는 최소 걸은 시간의 합(초)을 정수 하나로 출력한다.

제한

$1 \le N \le 200\,000$
$0 \le P_i \le 1\,000\,000\,000$
$1 \le W_i \le 1000$
$0 \le D_i \le 1\,000\,000\,000$

예제3

예제 1
입력
```
1
0 1000 0
```
예상 출력
```
0
```
예제 2
입력
```
2
10 4 3
20 4 2
```
예상 출력
```
20
```
예제 3
입력
```
3
6 8 3
1 4 1
14 5 2
```
예상 출력
```
43
```