고장 난 자판기

면접 대비

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

요약

각 간식이 나오는 위치로 가장 싸게 누를 수 있는 버튼을 찾아 시장가보다 쌀 때만 전부 팔아 합산합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 배열
정답자: 아직 제출이 없습니다

문제

밥은 고장 난 자판기를 하나 발견했고, 이걸로 돈을 벌려고 한다. 자판기에는 1번부터 $n$ 번까지 번호가 붙은 자리가 $n$ 개 있다. $i$ 번 자리에는 과자가 $s_i$ 개 들어 있고, 버튼을 한 번 누르는 값은 $p_i$ 이며, 이 자리의 과자 하나는 시장에서 $m_i$ 에 팔린다.

자판기는 일정한 방식으로 고장 나 있다. 밥이 $i$ 번 자리의 버튼을 누르면 자판기는 $p_i$ 를 받고, $i$ 번이 아니라 $f(i)$ 번 자리에서 과자를 하나 내보낸다. $f(i)$ 번 자리가 이미 비어 있으면 밥은 값만 내고 아무것도 받지 못한다. $i$ 번 버튼을 눌러도 $i$ 번 자리의 과자 수는 줄지 않고, 과자가 나온 자리의 개수만 하나 줄어든다. 밥은 아무 버튼이나 원하는 순서로 몇 번이든 누를 수 있고, 누를 때마다 값을 낸다.

밥은 받은 과자를 모두 시장 가격에 판다. $j$ 번 자리에서 나온 과자는 $m_j$ 에 팔린다. 버튼을 누르는 값은 얼마든지 낼 수 있다. 밥이 얻을 수 있는 순이익의 최댓값을 구하여라. 순이익은 받은 과자의 시장 가격 합에서 낸 값의 합을 뺀 것이다. 버튼을 한 번도 누르지 않아도 된다.

입력

첫째 줄에 자리의 개수 $n$ 이 주어진다 ( $1 \le n \le 10^5$ ). 다음 $n$ 개 줄에는 1번 자리부터 $n$ 번 자리까지 차례로 각 자리의 정보가 네 정수 $f$ , $p$ , $m$ , $s$ 로 주어진다.

$f$ 는 이 자리의 버튼을 눌렀을 때 자판기가 과자를 내보내는 자리 번호 $f(i)$ 다 ( $1 \le f \le n$ ).
$p$ 는 이 자리의 버튼을 한 번 누르는 값이다 ( $1 \le p \le 10^6$ ).
$m$ 은 이 자리 과자의 시장 가격이다 ( $1 \le m \le 10^6$ ).
$s$ 는 이 자리에 들어 있는 과자의 개수다 ( $1 \le s \le 10^6$ ).

출력

첫째 줄에 밥이 얻을 수 있는 순이익의 최댓값을 정수 하나로 출력한다.

예제3

예제 1
입력
```
3
1 2 3 1
2 3 4 1
3 4 5 1
```
예상 출력
```
3
```
예제 2
입력
```
3
2 2 3 8
3 1 5 6
1 9 4 7
```
예상 출력
```
39
```

예제 3

입력

예상 출력