Trên hai đồ thị vô hướng, liên thông \(G_1\) và \(G_2\) cùng có \(n\) đỉnh. Với hai đỉnh \(s\) và \(t\), đặt robot thứ nhất ở đỉnh \(s\) trên đồ thị \(G_1\), robot thứ hai cũng ở đỉnh \(s\) trên đồ thị \(G_2\), tìm cách di chuyển hai robot cùng về đỉnh \(t\) như sau: Tại mỗi thời điểm, chọn một đỉnh \(v\), với mỗi robot, robot có thể lựa chọn di chuyển đến \(v\) nếu có cạnh hoặc không thực hiện di chuyển. Gọi \(d(s,t)\) là thời gian ngắn nhất để hai robot cùng đến được đỉnh \(t\).

Yêu cầu: Tính tổng các giá trị \(d(s,t)\) cho mọi cặp \((s,t)\).

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 500\)).
• Dòng tiếp theo chứa số nguyên dương \(m_1\) là số cạnh của đồ thị \(G_1\).
• Dòng thứ \(i\) (\(1 \le i \le m_1\)) trong \(m_1\) dòng sau, mỗi dòng chứa hai số nguyên \(x_i,y_i\) cho biết hai đỉnh \(x_i,y_i\) có cạnh nối trong đồ thị \(G_1\).
• Dòng tiếp theo chứa số nguyên dương \(m_2\) là số cạnh của đồ thị \(G_2\).
• Dòng thứ \(j\) (\(1 \le j \le m_2\)) trong \(m_2\) dòng sau, mỗi dòng chứa hai số nguyên \(u_j,v_j\) cho biết hai đỉnh \(u_j,v_j\) có cạnh nối trong đồ thị \(G_2\).

Output

• Gồm một dòng là tổng các giá trị \(d(s,t)\) cho mọi cặp \((s,t)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 500\).

Example

3
3
1 2
2 3
3 1
2
1 2
2 3

8

Alice được giao thực hiện \(n\) công việc, cô đã đánh số các công việc từ \(1\) đến \(n\) và tính toán công việc thứ \(i\) (\(1 \le i \le n\)) có đặc điểm như sau:

• Thời gian thực hiện là \(t_i\).
• Mức độ quan trọng là \(w_i\) nên nếu công việc \(i\) kết thúc tại thời điểm \(d\) thì sẽ mất chi phí \(d \times w_i\).
• Công việc \(p_i\) phải được thực hiện trước công việc \(i\) (\(p_i < i\)). Chỉ có duy nhất \(p_1 = 0\) nghĩa là chỉ có công việc \(1\) có thể thực hiện ngay thời điểm \(0\) đầu tiên.

Alice cần lập lịch để tổng chi phí thực hiện cả \(n\) công việc là nhỏ nhất. Tuy nhiên, Aliec có thể thay đổi trọng số của một công việc nào đó thành \(1\).

Yêu cầu: Hãy giúp Alice tìm cách thay đổi trọng số của một công việc để chi phí thực hiện của cả \(n\) công việc là nhỏ nhất.

Input

• Dòng đầu là số nguyên dương \(n\) là số công việc.
• Dòng thứ hai gồm \(n\) số mô tả mảng \(p\).
• Dòng thứ ba gồm \(n\) số nguyên không âm mô tả mảng \(w\) (\(w_i \le 10^3\)).
• Dòng cuối cùng gồm \(n\) số nguyên không âm mô tả mảng \(t\) (\(t_i \le 10^3\)).

Output

• Một dòng chứa một số là tổng chi phí nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 8\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 18\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 180\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 1800\).

Example

3
0 1 1
2 3 3
1 2 3

17

Một bức ảnh của một vật thể được biểu diễn bằng bảng số kích thước \(m \times n\), các hàng được đánh số từ \(1\) đến \(m\), các cột được đánh số từ \(1\) đến \(n\). Ô giao giữa hàng \(i\) (\(1 \le i \le m\)) và cột \(j\) (\(1 \le j \le n\)) được gọi là ô \((i,j)\) và có giá trị \(0\) hoặc \(1\) mô tả điểm ảnh. Vật thể là một vùng gồm các ô có giá trị \(1\) liên thông chung cạnh.

Do lưu trữ không cẩn thận, một số ô trên bảng không thể xác định được chính xác giá trị bằng \(0\) hay bằng \(1\). Tuy nhiên, người ta biết được trên hàng \(i\) (\(1 \le i \le m\)) có đúng \(a_i\) số \(1\); trên cột \(j\) (\(1 \le j \le n\)) có đúng \(b_j\) số \(1\).

Yêu cầu: Hãy khôi phục lại bảng số, nếu có nhiều khả năng chỉ cần đưa ra một phương án.

Input

• Dòng đầu chứa hai số nguyên \(m,n\) (\(m,n \le 100\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\), mỗi số nhận một trong ba giá trị \(0\) hoặc \(1\) hoặc \(-1\) (ô không xác định được giá trị).
• Tiếp theo là một dòng chứa \(m\) số \(a_1,a_2,...,a_m\).
• Cuối cùng là một dòng chứa \(n\) số \(b_1,b_2,...,b_n\).

Output

• Gồm \(m\) dòng, mỗi dòng chứa \(n\) số \(0\) hoặc \(1\) mô tả bảng số được khôi phục.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m,n \le 10\) và không quá \(10\) ô có giá trị \(-1\) trong bảng.
• Subtask \(2\) (\(30\%\) số điểm): \(m,n \le 30\) và không quá \(30\) ô có giá trị \(-1\) trong bảng.
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
1 0 0 1
-1 -1 -1 -1
1 0 0 1
2 4 2
3 1 1 3

1 0 0 1
1 1 1 1 
1 0 0 1

3 3
-1 -1 -1
-1 -1 -1
-1 -1 -1
3 2 3
3 2 3

1 1 1
1 0 1
1 1 1