1. Phát biểu bài toán

Để duy trì độ nổi ổn định qua ~N~ khoang từ trường liên tiếp, hệ thống điều khiển phải xác lập tại mỗi khoang thứ ~i~ (~1 \le i \le N~) một cặp thông số pha ~x_i, y_i \in \mathbb{R}^2~ (~x_i, y_i~ là các số thực) thỏa mãn đồng thời hai hệ điều kiện:

1. Điều kiện giới hạn biên tại từng khoang: Với mọi ~i \in \{1, 2, \dots, N\}~, điểm ~(x_i, y_i)~ phải nằm trong hình thoi tâm ~(A_i, B_i)~ bán kính ~R_i~ theo chuẩn ~L_1~:

$$ |x_i - A_i| + |y_i - B_i| \le R_i $$

1. Điều kiện liên tục pha giữa hai khoang kề nhau: Với mọi ~i \in \{1, 2, \dots, N-1\}~, độ dịch chuyển pha không vượt quá hằng số ~K_i~:

$$ |x_{i+1} - x_i| + |y_{i+1} - y_i| \le K_i $$

Chi phí điều chỉnh tại khoang thứ ~i~ so với điểm neo phụ ~(P_i, Q_i)~ được tính bằng khoảng cách Manhattan có trọng số ~W_i > 0~:

$$ \text{Cost}_i(x_i, y_i) = W_i \cdot (|x_i - P_i| + |y_i - Q_i|) $$

Yêu cầu: Hãy tìm dãy các cặp số thực ~(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)~ thỏa mãn cả hai hệ điều kiện trên sao cho tổng chi phí ~\sum_{i=1}^N \text{Cost}_i(x_i, y_i)~ đạt giá trị nhỏ nhất. Nếu không tồn tại dãy nào thỏa mãn, hãy thông báo -1.

2. Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~N~ (~2 \le N \le 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa sáu số nguyên ~A_i, B_i, R_i, P_i, Q_i, W_i~ (~|A_i|, |B_i|, |P_i|, |Q_i| \le 10^8~; ~0 \le R_i \le 10^8~; ~1 \le W_i \le 10^4~).
• Dòng cuối cùng chứa ~N - 1~ số nguyên không âm ~K_1, K_2, \dots, K_{N-1}~ (~0 \le K_i \le 10^8~).

3. Kết quả

• Nếu không tồn tại phương án hợp lệ, in ra -1.
• Ngược lại, chứng minh được rằng tổng chi phí nhỏ nhất nhân với 2 luôn là một số nguyên. Hãy in ra giá trị nguyên của:

$$ (2 \times \text{Tổng chi phí nhỏ nhất}) $$

4. Ví dụ

Ví dụ 1:

• Input:

2
0 0 0 1 0 1
0 0 0 0 2 2
0

• Output:

10

Ví dụ 2:

• Input:

2
0 0 0 0 0 1
4 0 0 4 0 1
1

• Output:

-1

5. Subtasks

• Subtask 1 (20% số điểm): ~N \le 100~, ~R_i, K_i \le 100~.
• Subtask 2 (30% số điểm): ~B_i = Q_i = 0~ và ~y_i~ bắt buộc bằng 0 (bài toán 1 chiều).
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm (~N \le 10^5~).