Học viện JOI tổ chức một buổi trao đổi bánh kẹo vào dịp ngày Valentine trắng. Có \(N\) học sinh tham gia, được đánh số từ \(1\) đến \(N\). Mỗi học sinh chọn làm một trong hai loại bánh: bánh quy hoặc bánh kem, rồi tặng cho một học sinh khác. Học sinh \(i\) tặng \(B_i\) chiếc bánh mình làm cho học sinh \(A_i\).

Mỗi học sinh có sở thích riêng. Với học sinh \(i\):

• Mỗi chiếc bánh nhận được cùng loại với bánh mình làm đem lại \(C_i\) điểm vui vẻ.
• Mỗi chiếc bánh nhận được khác loại với bánh mình làm đem lại \(D_i\) điểm vui vẻ.

Điểm vui vẻ của mỗi học sinh là tổng điểm từ tất cả bánh người đó nhận được. Một học sinh có thể nhận bánh từ nhiều người hoặc không nhận được chiếc nào. Các hệ số \(C_i,D_i\) thuộc về người nhận bánh.

Yêu cầu

Chọn loại bánh mỗi học sinh làm sao cho tổng điểm vui vẻ của cả \(N\) học sinh lớn nhất, và tính giá trị lớn nhất đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa bốn số nguyên \(A_i,B_i,C_i,D_i\), phân cách bằng dấu cách: người nhận bánh từ học sinh \(i\), số bánh học sinh \(i\) tặng, điểm học sinh \(i\) nhận được cho mỗi bánh cùng loại và điểm học sinh \(i\) nhận được cho mỗi bánh khác loại.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng điểm vui vẻ lớn nhất của \(N\) học sinh.

Giới hạn

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) và \(A_i \ne i\) với mọi \(1 \le i \le N\).
• \(1 \le B_i,C_i,D_i \le 1\,000\,000\) với mọi \(1 \le i \le N\).
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 16\).
• Bài toán con 2 (20 điểm): \(N \le 5\,000\).
• Bài toán con 3 (70 điểm): Không có giới hạn bổ sung.

Ví dụ

7
3 3 6 5
7 2 8 8
4 5 3 9
1 8 7 2
1 8 8 4
3 7 4 5
2 5 1 2

257

Cho các học sinh \(1,2,5,6\) làm bánh quy và các học sinh \(3,4,7\) làm bánh kem. Khi đó:

• Học sinh \(1\) nhận \(8\) bánh quy và \(8\) bánh kem, được \(88\) điểm.
• Học sinh \(2\) nhận \(5\) bánh kem, được \(40\) điểm.
• Học sinh \(3\) nhận \(10\) bánh quy, được \(90\) điểm.
• Học sinh \(4\) nhận \(5\) bánh kem, được \(35\) điểm.
• Học sinh \(5\) không nhận bánh, được \(0\) điểm.
• Học sinh \(6\) không nhận bánh, được \(0\) điểm.
• Học sinh \(7\) nhận \(2\) bánh quy, được \(4\) điểm.

Tổng điểm vui vẻ là \(257\).