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ột 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 giữa 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 gói quà thứ ~i~ cho Bắc, số thứ ~i~ bằng ~2~ thì ông chia gói 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ách 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 75% điểm với ~1 < N \le 20~;
• Có 25% test tương ứng 25% điểm với ~20 < N \le 100~.

Ví dụ

Ví dụ 1

INPUT

5
10 15 14 8 10
1 2 1 2 1

OUTPUT

11
1