Có $N$ đống đá xếp thành một hàng, đống thứ $i$ có $w_i$ viên đá và có màu $c_i$ ($0$, $1$ hoặc $2$).

Nếu hai đống đá liền kề có cùng màu, có thể gộp chúng thành một đống; số viên đá của đống mới bằng tổng số viên đá của hai đống, và màu trở thành $(c + 1) \mod 3$.

Hãy tìm số đống ít nhất có thể đạt được cuối cùng, và trong trường hợp số đống ít nhất, tổng chi phí nhỏ nhất (chi phí của mỗi lần gộp bằng tổng số viên đá của hai đống).

Dữ liệu vào

Dòng đầu tiên là một số nguyên $N$.

Dòng thứ hai gồm $N$ số nguyên $w_1, w_2, \ldots, w_N$.

Dòng thứ ba gồm $N$ số nguyên $c_1, c_2, \ldots, c_N$.

Dữ liệu ra

In ra hai số nguyên, lần lượt là số đống ít nhất và chi phí nhỏ nhất.

Ví dụ

Input

Output

Ghi chú

Phạm vi dữ liệu

• $1 \le N \le 300$
• $1 \le w_i \le 10^4$
• $0 \le c_i \le 2$