Trong căn hầm tối của giáo sư Acidrain có hai ngăn kéo đựng găng tay: một ngăn đựng găng trái và một ngăn đựng găng phải. Mỗi ngăn có găng thuộc \(n\) màu. Giáo sư biết số găng của từng màu trong mỗi ngăn và biết chắc tồn tại ít nhất một cặp găng trái–phải cùng màu.

Trong hầm tối, ông không thể nhận ra màu của bất kỳ chiếc găng nào. Trước khi xuống hầm, ông phải quyết định chính xác sẽ lấy bao nhiêu găng từ mỗi ngăn sao cho, bất kể những chiếc cụ thể được lấy là gì, chắc chắn có ít nhất một cặp trái–phải cùng màu. Ông muốn tổng số găng phải mang lên là nhỏ nhất.

Hãy tìm một cặp số lượng tối ưu cần lấy từ hai ngăn.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) — số màu (\(1\le n\le20\)).

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(0\le a_i\le10^8\)), trong đó \(a_i\) là số găng trái màu \(i\).

Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,\ldots,b_n\) (\(0\le b_i\le10^8\)), trong đó \(b_i\) là số găng phải màu \(i\).

Dữ liệu ra

Dòng đầu chứa số găng cần lấy từ ngăn găng trái. Dòng thứ hai chứa số găng cần lấy từ ngăn găng phải.

Tổng hai số phải nhỏ nhất có thể. Nếu có nhiều đáp án đúng, có thể in bất kỳ đáp án nào.

Phân nhóm

1. 40 điểm: \(n\le4\) và \(a_i,b_i\le10\) với mọi \(i\).
2. 60 điểm: không có ràng buộc bổ sung.

Ví dụ

4
0 7 1 6
1 5 0 6

2
8