Tí và Tèo nghĩ ra một trò chơi với các viên sỏi. Trò chơi gồm ~n~ viên sỏi được đánh số thứ tự từ ~1~ đến ~n~. Mỗi viên sỏi có khối lượng ~w_i~ và trên đó ghi một giá trị ~v_i~. Số viên sỏi được chia cho hai bạn sao cho mỗi bạn phải có ít nhất một viên và không cần thiết chia hết số sỏi đang có. Ngoài ra, tổng khối lượng sỏi của hai bạn phải bằng nhau. Sau khi chia xong, mỗi bạn chọn ra trong số sỏi của mình một viên có giá trị lớn nhất làm quân tướng. Nếu có nhiều viên cùng giá trị lớn nhất thì bất kỳ viên nào trong đó cũng có thể được chọn làm quân tướng. Độ chính xác của mỗi cách chia sỏi được đánh giá bằng độ lệch giá trị giữa hai quân tướng của hai bạn.

Yêu cầu: Tìm độ chính xác lớn nhất có thể trong các cách chia sỏi.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 500)~ là số viên sỏi;

• Dòng thứ hai chứa ~n~ số nguyên dương ~w_1, w_2, \dots, w_n~ ~(1 \le w_1 + w_2 + \dots + w_n \le 3 \cdot 10^5)~ với ~w_i~ là khối lượng của viên sỏi thứ ~i~ ~(1 \le i \le n)~;

• Dòng thứ ba chứa ~n~ số nguyên dương ~v_1, v_2, \dots, v_n~ ~(1 \le v_i \le 10^9)~ với ~v_i~ là giá trị được ghi trên viên sỏi thứ ~i~ ~(1 \le i \le n)~.

Dữ liệu luôn đảm bảo tồn tại cách chia để tổng khối lượng sỏi của hai bạn bằng nhau.

Output

Ghi ra một số nguyên duy nhất là độ chính xác lớn nhất có thể đạt được.

Scoring

Sample Input 1

8
8 3 5 7 13 7 4 13
2 3 4 9 3 2 8 1

Sample Output 1

7

Notes

• Tí có thể được chia viên sỏi số ~1~ và ~8~ với tổng khối lượng ~= 8 + 13 = 21~ và lấy viên sỏi số ~1~ làm quân tướng với giá trị là ~2~.

• Tèo có thể được chia viên sỏi số ~2, 4, 6, 7~ với tổng khối lượng ~= 3 + 7 + 7 + 4 = 21~ và lấy viên sỏi số ~4~ làm quân tướng với giá trị là ~9~.