Cho một chiếc đồng hồ ~12~ giờ gồm có kim giờ và kim phút.

Hiện tại đồng hồ đang chỉ ~a~ giờ ~b~ phút. Hỏi sau bao nhiêu phút nữa đồng hồ sẽ chỉ ~9~ giờ đúng?

Input

Gồm một dòng duy nhất chứa hai số tự nhiên ~a~ và ~b~ (~0 \le a \le 11~, ~0 \le b \le 59~).

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

7 21

Sample Output 1

99

Giải thích: Đồng hồ hiện tại đang chỉ ~7~ giờ ~21~ phút. Vậy sau ~99~ phút nữa đồng hồ sẽ chỉ ~9~ giờ đúng.

Sample Input 2

9 0

Sample Output 2

0

Giải thích: Đồng hồ hiện tại đang chỉ ~9~ giờ đúng, nên đáp án là ~0~.

Gần trường của An có một cứa hàng hoa. Cửa hàng hoa ấy có giá bán hoa như sau:

• Bông hoa đầu tiên có giá ~1~ đồng.
• ~2~ bông hoa tiếp theo, mỗi bông có giá ~2~ đồng.
• ~3~ bông hoa tiếp theo, mỗi bông có giá ~3~ đồng.
• ...

An cần mua ~n~ bông hoa để chuẩn bị cho liên hoan lớp. Hỏi số tiền ít nhất An cần bỏ ra để mua đủ ~n~ bông hoa là bao nhiêu?

Input

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

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

5

Sample Output 1

11

Giải thích: Giá của từng bông hoa lần lượt là ~1~, ~2~, ~2~, ~3~, ~3~. Vậy An cần ít nhất ~1 + 2 + 2 + 3 + 3 = 11~ đồng để mua hoa.

Sample Input 2

10

Sample Output 2

30

Giải thích: Giá của từng bông hoa lần lượt là ~1~, ~2~, ~2~, ~3~, ~3~, ~3~, ~4~, ~4~, ~4~, ~4~.

Con phố nhà Bình đang chuẩn bị đón Trung Thu! Chính vì vậy, trên con phố hiện tại đang được treo ~n~ chiếc đèn lồng, mỗi chiếc có thể sáng màu vàng hoặc màu đỏ. Ban đầu, tất cả các chiếc đèn lồng đều đang sáng màu vàng.

Bình sẽ thực hiện ~n~ thao tác. Với mỗi thao tác thứ ~i~, Bình sẽ thay đổi màu của chiếc đèn lồng ở các vị trí chia hết cho ~i~ (từ màu vàng sang màu đỏ hoặc từ màu đỏ sang màu vàng). Hỏi sau ~n~ thao tác, có bao nhiều chiếc đèn đang sáng màu đỏ?

Input

Gồm một dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^{18}~).

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

5

Sample Output 1

2

Giải thích: Bình sẽ thực hiện 5 thao tác:

Màu của các đèn lồng ban đầu: Vàng, Vàng, Vàng, Vàng, Vàng

Màu của các đèn lồng sau thao tác thứ nhất: Đỏ, Đỏ, Đỏ, Đỏ, Đỏ

Màu của các đèn lồng sau thao tác thứ hai: Đỏ, Vàng, Đỏ, Vàng, Đỏ

Màu của các đèn lồng sau thao tác thứ ba: Đỏ, Vàng, Vàng, Vàng, Đỏ

Màu của các đèn lồng sau thao tác thứ tư: Đỏ, Vàng, Vàng, Đỏ, Đỏ

Màu của các đèn lồng sau thao tác thứ năm: Đỏ, Vàng, Vàng, Đỏ, Vàng

Vậy sau ~n~ thao tác, có ~2~ chiếc đèn tại vị trí ~1~ và ~4~ đang sáng màu đỏ.

Cho một mảng ~a~ gồm có ~n~ phần tử.

Ta quy ước việc ghép ba số bất kì là việc viết các số liên tiếp nhau theo thứ tự bất kì.

Ví dụ: Với ba số ~123~, ~45~, ~678~, ta có thể ghép ba số này thành các số:

• ~12345678~
• ~12367845~
• ~45123678~
• ~45678123~
• ~67812345~
• ~67845123~

Chọn ba số bất kì từ mảng ~a~. Hỏi giá trị lớn nhất ta có thể nhận được từ việc ghép số ba số đó là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ - số lượng phần tử của mảng ~a~ (~3 \le n \le 2*10^5~).

Dòng tiếp theo chứa ~n~ số nguyên dương - các phần tử của mảng ~a~ (~a_i \le 10^9~, ~i = 1...n~)

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

5
6 1 8 10 9

Sample Output 1

9810

Giải thích: Ta chọn ba số ~9~, ~8~, ~10~ và sau đó ghép thành số ~9810~. Đây là số lớn nhất ta có thể ghép được.

Cho dãy số ~a~ nguyên không âm gồm ~n~ phần tử ~a_1~, ~a_2~, ~a_3~,~...~,~a_n~ và số nguyên dương ~k \le n~.

Hãy tìm cách chia dãy số thành ~k~ đoạn con liên tiếp sao cho chênh lệch giữa đoạn có tổng các phẩn tử lớn nhất và đoạn có tổng các phần tử nhỏ nhất là bé nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~k \le n \le 250~, ~k \le 50~).

Dòng tiếp theo chứa các phần tử của dãy ~a~ (~0 \le a_i < 10^6~, ~i=1,2,..n~).

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

6 3
7 4 6 1 2 10

Sample Output 1

2

Giải thích: Ta chia thành ba đoạn như sau: ~[7,4]~, ~[6,1,2]~, ~[10]~.

Các đoạn lần lượt có tổng là ~11~, ~9~, ~10~. Vậy độ chênh lệch của cách chia này là ~2~.

Có thể chứng minh rằng không tồn tại cách chia nào khác có độ chênh lệch nhỏ hơn ~2~, do đó, chênh lệch nhỏ nhất có thể là ~2~.