Một số nguyên dương ~N~ được gọi là số đẹp nếu thỏa mãn các điều kiện sau:

• Số đó là số chính phương;
• Tổng các chữ số của nó là một số Fibonacci.

Yêu cầu

Cho số nguyên dương ~N~, đếm số lượng số đẹp nhỏ hơn hoặc bằng ~N~.

Dữ liệu đầu vào

Gồm một số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số lượng số đẹp nhỏ hơn hoặc bằng ~N~.

Ràng buộc dữ liệu

• Có 60% số test của bài thỏa mãn ~N \le 10^6~.
• Có 40% số test của bài không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

50

OUTPUT

2

Giải thích: Có ~2~ số thỏa yêu cầu đề bài là ~1~ và ~49~.

Thầy Minh tổ chức buổi phát thưởng cho các em học sinh đạt giải trong kỳ thi học sinh giỏi môn Tin. Thầy có ~X~ chiếc bút và ~Y~ quyển tập, thầy sẽ phát hết các phần thưởng cho các bạn học sinh và mong muốn số chiếc bút và số quyền tập được chia đều cho các bạn.

Yêu cầu

Cho hai số nguyên dương ~X~ và ~Y~. Hãy tìm tất cả các cách phát quà thỏa mãn điều kiện của thầy Minh.

Dữ liệu đầu vào

Gồm một dòng chứa hai số nguyên dương ~X, Y~ ~(X \le 10^{14},\ Y \le 10^{14})~.

Dữ liệu đầu ra

Gồm một số nguyên là số cách phát quà thỏa điều kiện đề bài.

Ràng buộc dữ liệu

• Có 60% số test của bài có ~X \le 10^6;\ Y \le 10^6~.
• Có 40% số test không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 6

OUTPUT

2

Giải thích: Với ~4~ chiếc bút và ~6~ quyển tập thì có các cách phát quà:

• Cách ~1~: phát quà cho ~1~ học sinh, mỗi em nhận ~4~ chiếc bút và ~6~ quyển tập.
• Cách ~2~: phát quà cho ~2~ học sinh, mỗi em nhận ~2~ chiếc bút và ~3~ quyển tập.

Vậy có ~2~ cách phát quà.

Cho một dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~.

Yêu cầu

Hãy tìm đoạn con ~[l, r]~ ~(1 \le l \le r \le N)~ gồm các phần tử liên tiếp ~a_l, a_{l + 1}, ..., a_{r - 1}, a_r~ của dãy ~A~ sao cho tổng ~a_l + a_{l + 1} + ... + a_{r - 1} + a_r~ là lớn nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^5)~ là số phần tử trong dãy.
• Dòng tiếp theo chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(|a_i| \le 10^9,\ 1 \le i \le N)~.

Dữ liệu đầu ra

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

Ràng buộc dữ liệu

• 20% số test của bài có ~N \le 100~.
• 20% số test của bài có ~N \le 10^4~.
• 20% số test của bài có ~N \le 10^5~ và ~a_i \ge 0~ ~(1 \le i \le N)~.
• 40% số test của bài có ~N \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

6
2 -3 8 4 -5 3

OUTPUT

12

Giải thích: ~a_3 + a_4 = 8 + 4 = 12~.

Vườn hoa của nhà Minh nở rộ ~N~ khóm hoa đẹp, khóm hoa thứ ~i~ có ~A_i~ bông hoa. Do nhu cầu của dịp lễ 8/3 lớn nên người lái buôn muốn mua càng nhiều hoa của vườn càng tốt. Tuy nhiên địa hình vườn nhà Minh không thể cắt hoa của ~K~ khóm hoa liên tiếp, vì vậy Minh cần tìm cách cắt hoa sao cho cắt được tổng số bông hoa là nhiều nhất có thể.

Yêu cầu

Hãy xác định số lượng bông hoa nhiều nhất có thể cắt được.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(2 \le K \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, A_3, ..., A_N~ ~(1 \le A_i \le 10^9)~ lần lượt là số bông hoa của mỗi khóm hoa.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng số bông hoa nhiều nhất có thể cắt được.

Ràng buộc dữ liệu

• 40% số test của bài có ~K = 3~.
• 40% số test tiếp theo có ~N \le 10^3;\ K \le 10^3~.
• 20% số test tiếp theo có ~N \le 10^5;\ K \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

7 3
2 4 1 5 3 1 6

OUTPUT

20

Giải thích: Vì không thể cắt hoa ở ~3~ khóm hoa liên tiếp nên Minh sẽ cắt hoa ở những khóm hoa thứ ~1, 2, 4, 5, 7~. Tổng số bông hoa cắt được là ~2 + 4 + 5 + 3 + 6 = 20~ bông hoa.

Ví dụ 2

INPUT

5 2
10 4 7 3 4

OUTPUT

21

Giải thích: Vì không thể cắt hoa ở ~2~ khóm hoa liên tiếp nên Minh sẽ cắt hoa ở những khóm hoa thứ ~1, 3~ và ~5~. Tổng số bông hoa cắt được là ~10 + 7 + 4 = 21~ bông hoa.