Cuộc phiêu lưu

Trong thế giới phép thuật, một người gác cổng trẻ tuổi tên là Minh được giao nhiệm vụ bảo vệ \(n\) cánh cổng thần bí, được đánh số từ \(1\) đến \(n\). Tại mỗi cánh cổng thứ \(i\) có một chiếc hộp chứa kho báu và một lò xo dịch chuyển.

• Lò xo có độ đàn hồi có thể điều chỉnh trong một khoảng \([L_i, H_i]\).
• Bốn loại báu vật được cất giữ, đánh số từ \(1\) đến \(4\), mỗi loại có một giá trị nhất định.

Để mở hộp, Minh cần dùng một chìa khóa ma thuật là một chuỗi 4 bit. Mỗi bit 1 tương ứng với việc lấy một loại báu vật. Ví dụ, với chìa khóa \(0110\), Minh sẽ nhận được báu vật loại \(2\) và \(3\).

Sau khi lấy kho báu, Minh sẽ dùng lò xo để dịch chuyển đến một cánh cổng khác. Nếu điều chỉnh độ đàn hồi của lò xo là \(k\) (\(k \in [L_i, H_i]\)), anh ta sẽ dịch chuyển đến cổng \(i+k\). Nếu \(i+k > n\), anh ta sẽ dịch chuyển ra khỏi khu vực bảo vệ.

Có một số quy tắc đặc biệt mà Minh phải tuân thủ:

• Chìa khóa không được có hai bit \(1\) liền kề.
• Hai chìa khóa sử dụng liên tiếp không được có bit \(1\) ở cùng một vị trí. Ví dụ, nếu vừa dùng chìa \(0010\) thì chìa \(1010\) ở bước tiếp theo sẽ không hợp lệ.
• Minh phải lấy ít nhất một loại báu vật.
• Hành trình của Minh chỉ kết thúc khi anh ta dịch chuyển ra khỏi khu vực bảo vệ.

Minh bắt đầu từ cánh cổng \(1\). Anh ta muốn đi qua các cổng và thu thập báu vật một cách hợp lệ để đạt được tổng giá trị lớn nhất có thể.

Yêu cầu:
Hãy tính tổng giá trị báu vật lớn nhất mà Minh có thể thu thập.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(n \le 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(6\) số nguyên: \(L_i, H_i\) và giá trị của \(4\) món báu vật ở cổng thứ \(i\) \((0 < L_i \le H_i \le 10^9)\). Giá trị của các món báu vật có giá trị tuyệt đối nhỏ hơn hoặc bằng \(10^9\).

Output

• Một số nguyên duy nhất là giá trị tối đa có thể thu thập.

Example

6
1 1 3 2 -4 5
1 2 2 -3 1 3
2 2 1 1 -1 -1
1 3 -10 10 30 33
1 1 2 3 -5 4
1 100 2 2 2 2

59

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 10\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(L_i = H_i\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.