Cho một bàn cờ ~n \times n~ và vô hạn các viên gạch ~1 \times 2~. Bạn được phép đặt các viên gạch ngang hoặc dọc vào bàn cờ sao cho không có viên gạch nào đè lên nhau, các viên gạch phải nằm trong bàn cờ.

Hãy in ra YES nếu có thể dùng vô hạn các viên gạch lấp đầy bàn cờ; ngược lại, in ra NO.

Input

Một dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^9~).

Output

In ra YES nếu bạn có thể lấp đầy bàn cờ với các viên gạch; ngược lại, in ra NO.

Sample Input 1

1

Sample Output 1

NO

Sample Input 2

2

Sample Output 2

YES

Đào là một người nông dân chăm chỉ và đang muốn mua càng nhiều bao hạt giống càng tốt để gieo trồng. Mỗi bao hạt giống có giá ~p~ đồng. Tuy nhiên, chính quyền áp dụng hai loại phí riêng cho hoạt động này:

• Cứ mỗi ~n_1~ bao hạt giống mua vào, bạn phải trả thêm ~t_1~ đồng phí bảo vệ môi trường.

• Cứ mỗi ~n_2~ bao hạt giống mua vào, bạn phải trả thêm ~t_2~ đồng phí kiểm định chất lượng.

Ví dụ: nếu ~n_1 = 2~ và ~n_2 = 4~, khi bạn mua ~4~ bao hạt giống thì phải nộp tổng cộng ~2 \times t_1 + t_2~ đồng phí.

Biết rằng Đào đang có ~C~ đồng trong tay, bạn hãy giúp Đào xác định số bao hạt giống tối đa mà Đào có thể mua được sau khi đã tính cả tiền hàng và hai loại phí kể trên.

Input

Một dòng duy nhất chứa sáu số nguyên dương ~C, p, n_1, n_2, t_1, t_2~.

Dữ liệu đảm bảo ~1 \le p,\ t_1,\ t_2 \le 100, \ 1 \le n_1 < n_2 \le 100~.

Output

Gồm một số nguyên duy nhất là kết quả.

Scoring

Sample Input 1

80 10 2 4 10 20

Sample Output 1

4

Sample Input 2

5950 33 30 84 46 7

Sample Output 2

172

Notes

Ở ví dụ 1, khi mua ~4~ bao hạt giống, Đào phải trả ~4 \times 10 = 40~ đồng cho ~4~ bao và ~2 \times 10 + 1 \times 20 = 40~ cho số tiền thuế. Vậy tổng tiền phải trả là ~80~.

Đào hiện tại đang có một dãy ~a~ có ~n~ phần tử và một số nguyên ~x~. Hiện tại Đào đang muốn thực hiện thao tác sau nhiều nhất một lần: nhân một đoạn con của chính dãy này với ~x~.

Yêu cầu: Biết rằng một đoạn con là một dãy các phần tử liên tiếp nhau trong một dãy số, hãy tính xem tổng đoạn con lớn nhất là bao nhiêu sau khi Đào thực hiện thao tác nhiều nhất một lần.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~x~ (~n ≤ 10^5, |x| ≤ 1000~) — lần lượt là độ dài của dãy ~a~ và số ~x~.

Dòng thứ hai gồm một dãy nguyên ~a_1,a_2,...,a_n (1 ≤ |a_i| ≤ 1000)~ — giá trị thứ ~i~ của dãy ~a~

Output

Gồm một số nguyên duy nhất là tổng đoạn con lớn nhất tìm được.

Scoring

Sample Input 1

5 2
-1 2 -1 3 -3

Sample Output 1

8

Sample Input 2

5 2
-1 -2 -3 -4 -5

Sample Output 2

-1

Notes

• Ở ví dụ thứ nhất, nhân đoạn con bắt đầu từ vị trí ~1~ đến ~4~, dãy số mới ta nhận được là ~[-2, 4, -2, 6, -3]~. Tổng đoạn con lớn nhất tìm được là ~[4, -2, 6] = 8~ với vị trí bắt đầu từ ~2~ cho đến ~4~.
• Ở ví dụ thứ hai, Đào chọn không nhân ~x~ với bất kì đoạn con nào. Khi đó, tổng đoạn con lớn nhất tìm được là ~[-1]~ có tổng là ~-1~.

Ở thị trấn Thuật Toán, hai người bạn Hiếu và Đức có một bảng số gồm các giá trị nguyên dương ~A_1, A_2, \ldots, A_N~. Hai bạn này thường hay ngồi chơi trò "Thằng nào khôn hơn" để tỉ thí xem ai là người giỏi hơn, đồng thời phát triển tư duy chiến lược "game theory" để trở thành những nhà toán học tài ba. Quy tắc như sau:

• Hiếu đi trước, chọn một vị trí ~x~ trong đoạn ~[L, R]~.

• Đức đi sau, chọn một vị trí ~y~ trong đoạn ~[L, R]~.

• Gọi ~u = \min(x, y)~ và ~v = \max(x, y)~. Điểm số của lần chơi là số đoạn con liên tiếp không giảm ~[i, j]~ thỏa ~u \leq i \leq j \leq v~, tức là số cặp ~(i, j)~ sao cho ~u \leq i \leq j \leq v~ và ~A_i \leq A_{i+1} \leq \ldots \leq A_j~.

Hiếu muốn điểm số là nhỏ nhất có thể, còn Đức muốn điểm số là lớn nhất có thể, biết rằng cả hai đều chơi tối ưu. Do hai bạn trẻ của chúng ta rất hiếu chiến nên họ đấu với nhau tận ~Q~ lần, mỗi lần họ sẽ chọn ra một dãy con liên tiếp ~A_L, A_{L+1}, \ldots, A_R~ để chơi. Với mỗi lần chơi như vậy, bạn cần cho biết điểm số của trò chơi nếu cả hai đều chơi tối ưu là bao nhiêu.

Input

• Dòng đầu chứa hai số nguyên ~N, Q~ — độ dài dãy và số truy vấn.

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~.

• Mỗi trong ~Q~ dòng tiếp theo chứa hai số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~, mô tả một ván chơi diễn ra trên đoạn ~A_L, A_{L+}1, \ldots, A_R~.

Output

In ra ~Q~ dòng. Dòng thứ i in một số nguyên — điểm số sau khi Hiếu và Đức cùng chơi tối ưu trên đoạn ~A_L, A_{L+}1, \ldots, A_R~.

Scoring

Sample Input 1

6 4
1 4 2 5 7 6
1 4
2 5
1 6
1 3

Sample Output 1

4
4
6
3

Notes

Ở truy vấn thứ nhất, nếu Hiếu chọn ~x = 2~ thì Đức sẽ chọn ~y = 4~, các dãy con không giảm sẽ là ~(4), (2), (5), (2, 5)~. Nếu Hiếu chọn ~x = 3~ thì Đức sẽ chọn ~y = 1~, các dãy con không giảm sẽ là ~(1), (4), (2), (1, 4)~. Hiếu sẽ không chọn ~x = 1~ hoặc ~x = 4~ vì các nước đi này không tối ưu.

"Giữa rừng linh mộc, mỗi thân cây mang trong mình năng lượng nguyên thủy. Khi các dòng năng lượng giao hòa, chỉ những đường truyền thuần khiết mới dẫn đến sự cân bằng tuyệt đối của khu rừng."

Tại trung tâm khu rừng cổ, có ~n~ linh mộc được liên kết với nhau bằng ~n-1~ đường rễ ngầm, từ đó tạo thành một mạng cây gồm ~n~ đỉnh. Mỗi linh mộc ~v~ mang trong mình năng lượng nguyên thủy được tính bằng một số nguyên dương ~a_v~. Một đường dẫn năng lượng là dãy các đỉnh liên tiếp (không lặp lại) được nối lại với nhau bằng các đường rễ ngầm giữa hai linh mộc trong cây. Đường dẫn chỉ gồm duy nhất một linh mộc cũng được tính. Ta gọi năng lượng tổng hợp trên đường dẫn ~P~ được tính bằng cách lấy giá trị ước chung lớn nhất của tất cả các linh mộc trên ~P~. Cụ thể hơn, giá trị năng lượng được tính như sau:

$$ ~G(P) = \gcd(a_v : v \in P)~ $$

Một đường dẫn ~P~ được các hiền nhân cho là thuần khiết nếu như ~G(P) = 1~, và họ muốn đếm xem tồn tại bao nhiêu đường dẫn như vậy.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 2 \cdot 10^5~) — số lượng linh mộc trong khu rừng.
Dòng tiếp theo gồm một dãy số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \leq a_v \leq 2 \cdot 10^5~) — lần lượt là năng lượng nguyên thủy của linh mộc ~v~.
Trong ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_j~ và ~v_j~ — tồn tại rễ ngầm thứ ~j~ được nối giữa hai linh mộc ~u_j~ và ~v_j~.

Output

Gồm một số nguyên duy nhất là số đường dẫn thuần khiết trong khu rừng.

Scoring

Sample Input

5
1 2 3 4 5
1 2
2 3
2 4
1 5

Sample Output

10

Notes

• Các cặp đỉnh mà đường đi giữa chúng thỏa mãn yêu cầu đề bài là: ~(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)~.