Thẻ nhảy

Trên một dải băng vô hạn, các ô được đánh số bởi các số nguyên (âm, không và dương). Ban đầu bạn đứng ở ô $0$.

Có $n$ tấm thẻ. Thẻ thứ $i$ có độ dài $l_i$ và giá $c_i$. Nếu trả $c_i$ đồng, bạn được dùng thẻ thứ $i$: khi đó từ ô $x$ bất kỳ bạn có thể nhảy tới ô $x-l_i$ hoặc ô $x+l_i$.

Bạn muốn mua một tập thẻ sao cho xuất phát từ ô $0$, bạn có thể tới được mọi ô của dải băng (được phép đi qua các ô trung gian). Hãy tìm tổng chi phí nhỏ nhất để làm được điều đó, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số tấm thẻ.
• Dòng thứ hai chứa $n$ số nguyên $l_1,l_2,\dots ,l_n$: độ dài nhảy của từng thẻ.
• Dòng thứ ba chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$: giá của từng thẻ.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất. Nếu không thể mua tập thẻ nào thoả mãn, in ra $-1$.

Ràng buộc

• $1\le n\le 300$
• $1\le l_i\le {10}^9$
• $1\le c_i\le {10}^5$

Ví dụ