Cho một số tự nhiên ~X~ và ~K~. Hãy tìm số tự nhiên ~Y~ bé nhất sao cho ~X \times Y~ có ít nhất ~K~ số ~0~ tận cùng.

Input

• Dòng ~1~ chứa một số tự nhiên ~X~;
• Dòng ~2~ chứa một số tự nhiên ~K~.

Output

• Ghi ra một số tự nhiên ~Y~ nhỏ nhất thoả mãn điều kiện đề bài.

Example

Sample input 1

6
2

Sample output 1

50

Giải thích

~6 \times 50 = 300~

Giới hạn

• Nếu chương trình chạy đúng những trường hợp ~X \leq 100; K \leq 6~, thí sinh sẽ được ~60~ điểm;
• Nếu chương trình chạy đúng những trường hợp ~X \leq 10^9; K \leq 15~, thí sinh sẽ được ~100~ điểm.

Bạn có ~N~ que có độ dài khác nhau và cần tạo một số tam giác từ các que này. Một tam giác hợp lệ nếu diện tích của nó lớn hơn ~0~. Nhiệm vụ của bạn là tìm số cách có thể tạo một tam giác hợp lệ bằng cách sử dụng các que.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ (~3 \leq N \leq 2000~) - số lượng que.
• Dòng tiếp theo chứa ~N~ số nguyên biểu thị độ dài của các que. Bạn có thể giả sử rằng các độ dài là khác nhau và mỗi độ dài nằm trong khoảng [~1,10^9~].

Output

• In ra tổng số cách có thể tạo ra một tam giác hợp lệ.

Sample Test

Input:

4
100 211 212 121

Output:

4

Một băng chuyền có một số lượng ống chứa có dung tích khác nhau, mỗi ống đều đã được đổ đầy với sữa. Sữa từ băng chuyền này cần được chuyển vào ~m~ containers. Các ràng buộc như sau:

Khi sữa từ một ống được đổ vào một container, phải đổ hết sữa trong ống đó vào container đó. Tức là không thể đổ sữa từ cùng một ống vào các container khác nhau. Sữa từ ống phải được đổ vào container theo thứ tự xuất hiện của chúng trên băng chuyền. Tức là không thể chọn một ống Container thứ ~i~ phải được đổ sữa chỉ từ các ống xuất hiện trước các ống đổ sữa vào container thứ ~j~, với ~i < j~.

Cho số lượng containers ~m~, bạn cần đổ sữa từ tất cả các ống vào containers mà không để lại sữa trong bất kỳ ống nào. Các containers không nhất thiết phải có cùng dung tích. Nhiệm vụ của bạn là tìm dung tích nhỏ nhất có thể của container có dung tích lớn nhất.

Input

Dòng đầu chứa hai số nguyên ~n~ ~(1 \leq n \leq 1000)~, số lượng ống chứa trên băng chuyền và ~m~ ~(1 \leq m \leq 10^6)~, số lượng containers mà bạn phải chuyển sữa vào.

Dòng tiếp theo chứa dung tích ~c~ ~(1 \leq c \leq 10^6)~ của mỗi ống chứa theo thứ tự xuất hiện trên băng chuyền. Lưu ý rằng, sữa đã được đổ đầy trong các ống chứa. Vì vậy, dung tích của ống chứa bằng với lượng sữa trong đó.

Output

Đối với mỗi bài toán, in ra số thứ tự của bài toán và kết quả mong muốn. Xem ví dụ để biết định dạng chính xác.

Sample

Input

3 2
4 78 9

Output

82

Số nguyên dương ~d~ được gọi là ước của số nguyên dương ~N~ nếu ~N~ chia hết cho ~d~. Ví dụ: các ước của ~9~ là ~1, 3~ và ~9;~ các ước của ~10~ là ~1, 2, 5~ và ~10~.

Yêu cầu: Cho hai số nguyên dương ~L~ và ~R~ ~(L ≤ R)~. Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~ ~(~bao gồm cả ~L~ và ~R)~.

Dữ liệu:

Gồm một dòng chứa hai số nguyên dương ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^9).~

Kết quả:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~.

Ràng buộc

• Có ~20\%~ số test ứng với ~R ≤ 1000~;
• ~25\%~ số test khác ứng với ~R - L ≤ 1000~;
• ~25\%~ số test khác ứng với ~R ≤ 10^6~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn ~[9, 12]~ là: ~1, 2, 3, 4, 5, 6, 9, 10, 11~ và ~12~ ~(7~ và ~8~ không nằm trong danh sách này vì cả ~9, 10, 11~ và ~12~ đều không chia hết cho ~7~ hoặc ~8)~.

Ta có ~1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63~.

Input

7 7

Output

8

Giải thích

Các số là ước của ~7~ là ~1~ và ~7~. Ta có ~1 + 7 = 8~.

Cho dãy số nguyên ~a = (a_1, a_2, ..., a_n)~ bạn được thay số ~0~ trong ~a~ bởi một số nguyên bất kỳ khác sau đó chọn ra trong dãy ~a~ một số nhiều nhất các số (không cần đúng thứ tự) sao cho các số đã chọn tạo thành một dãy số nguyên liên tiếp.

Yêu cầu: Tìm cách có được dãy số nguyên liên tiếp dài nhất theo cách trên.

Ví dụ với ~a = (1, 0 ,3 ,8 ,5 ,9 ,0)~, ta có thể thay hai số ~0~ lần lượt bởi ~6~ và ~7~, khi đó có thể chọn trong ~a~ ra các số ~(5, 6, 7, 8, 9)~ để được dãy số nguyên liên tiếp dài nhất.

INPUT

Dòng 1 chứa số nguyên dương ~n \le 10^6~

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (giá trị ~i~: ~|a_i| \le 10^6~)

OUTPUT

Số nguyên duy nhất là độ dài dãy số nguyên liên tiếp thu được theo phương án của bạn.

SAMPLE INPUT

7
1 0 3 8 5 9 0

SAMPLE OUTPUT

5