화이트데이 선물 교환

JOI 학원에서는 매년 화이트데이에 맞춰 과자 선물 교환회를 연다. 올해 선물 교환회에는 1부터 N까지의 학생 번호가 붙은 N명의 학생이 참가한다. 각 학생은 자기 자신이 아닌 다른 학생 한 명을 위해 쿠키 또는 케이크 중 하나를 만든다. 번호 i인 학생은 번호 $A_i$인 학생에게 만든 과자를 $B_i$개 선물한다.

자기가 만든 것과 같은 종류의 과자를 받아 맛을 연구하고 싶어 하는 학생도 있고, 자기가 만든 것과 다른 종류의 과자(쿠키를 만들었다면 케이크, 케이크를 만들었다면 쿠키)를 받아 즐기고 싶어 하는 학생도 있다. 번호 i인 학생은 자기가 만든 것과 같은 종류의 과자를 1개 받을 때마다 "기쁨"이 $C_i$포인트 더해지고, 자기가 만든 것과 다른 종류의 과자를 1개 받을 때마다 "기쁨"이 $D_i$포인트 더해진다. N명의 학생이 쿠키 또는 케이크 중 무엇을 만들지 잘 선택했을 때, N명의 학생의 "기쁨" 합계는 최대 얼마가 될 수 있을까?

학생이 과자를 선물할 상대와 개수, 그리고 "기쁨" 정보가 주어졌을 때, "기쁨" 합계의 최댓값을 구하는 프로그램을 작성하라.

표준 입력에서 다음 입력을 읽는다.

• 1번째 줄에는 정수 N이 적혀 있으며, JOI 학원 학생의 수를 나타낸다.
• 이어지는 N개 줄 중 i번째 줄 (1 ≤ i ≤ N)에는 정수 $A_i$, $B_i$, $C_i$, $D_i$가 공백으로 구분되어 적혀 있으며, 번호 i인 학생은 번호 $A_i$ (1 ≤ $A_i$ ≤ N, $A_i$ ≠ i)인 학생에게 $B_i$개의 과자를 선물한다는 것, 자기가 만든 과자와 같은 종류의 과자를 받았을 때 얻는 "기쁨"이 $C_i$포인트, 다른 종류의 과자를 받았을 때 얻는 "기쁨"이 $D_i$포인트라는 것을 나타낸다.

표준 출력에 N명의 학생의 "기쁨" 합계의 최댓값을 1줄로 출력하라.

• 2 ≤ N ≤ 100 000.
• 1 ≤ $B_i$ ≤ 1 000 000 (1 ≤ i ≤ N).
• 1 ≤ $C_i$ ≤ 1 000 000 (1 ≤ i ≤ N).
• 1 ≤ $D_i$ ≤ 1 000 000 (1 ≤ i ≤ N).