Câu 4 (4.0 điểm). Chia quà

Bố của hai anh em Bắc và Giang vừa có một chuyến đi công tác về. Ông đã chuẩn bị \(N\) gói quà,
các gói quà được đánh số từ 1 đến \(N\), gói quà thứ \(i\) có giá trị là \(a_i\).

Ông sẽ chia hết số quà cho hai anh em Bắc và Giang.
Ông chia quà thành hai phần với tổng giá trị của từng phần là \(S_1\) và \(S_2\), độ chênh lệch giữa
hai phần quà là \(|S_1 - S_2|\).

Trước khi chia quà, ông đã ghi lần lượt các số 1 và 2 trên các gói quà.
Nếu gói quà ghi số 1 thì chia cho Bắc, số 2 thì chia cho Giang.

Ông muốn thay đổi cách chia sao cho độ chênh lệch là nhỏ nhất.

Input

Vào từ tệp văn bản CHIAQUA.INP gồm:

• Dòng 1 ghi số nguyên dương \(N\);
• Dòng 2 ghi \(N\) số \(a_1, a_2, \ldots, a_N\) \((1 \le a_i \le 10000)\);
• Dòng 3 ghi dãy gồm \(N\) số (1 hoặc 2) tương ứng với cách chia ban đầu.

Output

Ghi ra tệp văn bản CHIAQUA.OUT gồm:

• Dòng 1 ghi độ chênh lệch của cách chia ban đầu;
• Dòng 2 ghi độ chênh lệch nhỏ nhất tìm được.

Example

5
10 15 14 8 10
1 2 1 2 1

11
1

Scoring

• Subtask 1: Có 30 test (75%) tương ứng 3,0 điểm với \(1 < N \le 20\);
• Subtask 2: Có 10 test (25%) tương ứng 1,0 điểm với \(20 < N \le 100\).