Số T-Prime là số có đúng 3 ước. Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số T-Prime. Ví dụ: Cho N=40, x=3, y =30, dãy số từ 1 đến 40. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 30 có tất cả 2 số T-Prime là: 9 và 25.

Yêu cầu: Cho số nguyên dương ~N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số T-Prime từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1 ≤ N \le 10^7~, ~q≤10^5~).
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên(~1≤ x \le y \le N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số T-Prime từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

40 3
1 3
1 30
3 10

Output

0
3
2

Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i + 1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là ri.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

• Dòng đầu tiên chứa số N ~(1 \le N \le 10^5)~.
• Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. ~(1 \le t_i \le 30000)~
• Dòng thứ ba ghi N - 1 số nguyên dương ~r_1, r_2, ..., r_{N - 1}. (1 \le r_i \le 30000)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Input

4
5 7 8 4
50 50 50

Output

24

Một công ty có ~n~ sản phẩm, sản phẩm thứ i có chất lượng là ~a_i~ (~1\le a_i \le 10^6~). Mỗi ngày công ty phải giao đúng ~k~ sản phẩm nếu số sản phẩm của công ty nhiều hơn hoặc bằng ~k~, ngược lại phải giao hết số sản phẩm theo nguyên tắc:

• Ở ngày đầu tiên chất lượng sản phẩm được giao không nhỏ hơn 1.
• Ở ngày thứ hai chất lượng sản phẩm được giao không nhỏ hơn 2.
• Ở ngày thứ ba chất lượng sản phẩm được giao không nhỏ hơn 3. ………
• Ở ngày thứ i chất lượng sản phẩm được giao không nhỏ hơn i. ………
  Quá trình giao hàng sẽ dừng lại khi đã giao hết hàng, hoặc không thể giao được nữa. Do có chiến lược giao hàng tối ưu, nên công ty đã giao hết số sản phẩm.

Yêu cầu: Hãy tìm giá trị nhỏ nhất của ~k~.

Dữ liệu vào:

• Dòng đầu: Số nguyên dương ~n~ (~n < 10^6~)
• Dòng hai: Dãy số nguyên dương ~a_1, a_2, a_3,…, a_n~ (~a_i < 10^6~, ~1 \le i \le n~)

Dữ liệu ra:

• Một số nguyên duy nhất theo yêu cầu.

Ví dụ:

Input

7
3 1 4 2 3 4 4

Output

2

Giải thích:

• Nếu mỗi ngày công ty giao 1 sản phẩm thì còn lại ít nhất 3 sản phẩm. Chẳng hạn ngày đầu giao sản phẩm có chất lượng 1, ngày thứ hai giao sản phẩm có chất lượng là 2, ngày thứ ba giao sản phẩm có chất lượng là 3, ngày thứ tư giao sản phẩm có chất lượng là 4. Như vậy còn 3 sản phẩm không được giao là 3, 4, 4.
• Nếu mỗi ngày công ty giao 2 sản phẩm và do công ty có chiến lược hợp lí nên đã giao hết hàng, chẳng hạn: ngày đầu giao sản phẩm có chất lượng 1 và 2, ngày thứ hai giao 2 sản phẩm có chất lượng là 3, ngày thứ 3 giao 2 sản phẩm có chất lượng là 4, ngày thứ tư giao sản phẩm còn lại có chất lượng 4.

Giới hạn dữ liệu:

• 60% bộ test có ~n <10^3~;
• 40% bộ test không giới hạn gì thêm.