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 vì hai anh em đã động viên ông trong suốt quãng thời gian ông đi công tác. Ô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|\) và mỗi anh em sẽ nhận mộ trong hai phần quà đó.
Trước khi chia quà cho các con, ông đã ghi lần lượt các số \(1\) và \(2\) trên các gói quà, lúc chia nếu gói quà ghi số \(1\) thì ông chia cho Bắc, gói quà ghi số \(2\) ông chia cho Giang. Như vậy, độ chênh lệch của hai phần quà đã được xác định. Ông đã suy nghĩ và muốn chia quà cho các con để sao cho độ chênh lệch giữa hai phần quà là nhỏ nhất.

Yêu cầu

Hãy giúp bố của Bắc và Giang chia quà cho hai anh em sao cho độ chênh lệch hai phần quà là nhỏ nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng 1 ghi số nguyên dương \(N (1 \le N \le 100)\).
• Dòng 2 ghi \(N\) số \(a_1, a_2, ..., a_N (1 \le a_i \le 10000, i = 1..N)\);
• Dòng 3 ghi dãy gồm \(N\) số (số 1 hoặc số 2) tương ứng với cách chia quà ban đầu của bố Bắc và Giang (số thứ \(i\) bằng 1 thì ông chia quà thứ \(i\) cho Bắc, số thứ \(i\) bằng 2 thì ông chia quà thứ \(i\) cho Giang).

Dữ liệu đầu ra

Gồm hai dòng:
- Dòng 1 ghi độ chênh lệch của các chia ban đầu
- Dòng 2 ghi độ chênh lệch nhỏ nhất tìm được.

Ràng buộc dữ liệu

• Có 75% test tương ứng với 75% điểm với \(1 < N \le 20\).
• Có 25% test tương ứng với 25% điểm với \(20 < N \le 100\).

Ví dụ

5
10 15 14 8 10
1 2 1 2 1

11
1