Số trùng là một số tự nhiên mà chữ số đầu tiên trùng với chữ số cuối cùng. Ví dụ: 8, 66, 686, 8398, ...

Nhập vào một số tự nhiên N. Hãy đếm xem có bao nhiêu số trùng nhỏ hơn N.

Ví dụ: N = 124, có các số thoả mãn: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121. Vậy có 22 số thỏa mãn.

Input: Số tự nhiên N (N ≤ 10^9).

Output: Một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input:

124

Output:

22

Trung tâm dữ liệu có N luồng xử lý liên tiếp, luồng thứ i cần T_i miligiây để tính toán. Giám đốc kỹ thuật cần chia N luồng này thành đúng K nhóm liên tiếp nhau để giao cho K máy chủ xử lý song song. Thời gian hoàn thành của toàn bộ hệ thống bằng thời gian của máy chủ mất nhiều thời gian nhất. Hãy tìm cách chia sao cho thời gian hoàn thành của toàn hệ thống là nhỏ nhất có thể.

Input:

Dòng 1: Hai số nguyên N, K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Ti (1 <= Ti <= 10^4).

Output: Thời gian hoàn thành nhỏ nhất có thể đạt được.

Ví dụ:

Input:

5 3
2 4 1 3 5

Output:

6

(Giải thích: Chia thành [2, 4], [1, 3], [5]. Thời gian của 3 máy lần lượt là 6, 4, 5. Máy lâu nhất mất 6 miligiây).

Hai trạm thu phát vô tuyến ghi nhận được hai dãy tần số A (gồm N số) và B (gồm M số). Các chuyên gia cần tìm một dãy tần số phụ thỏa mãn 3 điều kiện: là dãy con của A, là dãy con của B, và là một dãy tăng ngặt. Hãy tìm độ dài của dãy con chung tăng ngặt dài nhất này.

Input:

Dòng 1: N, M (1 <= N, M <= 500).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Dòng 3: M số nguyên Bi (1 <= Bi <= 10^4).

Output: Độ dài lớn nhất tìm được.

Ví dụ:

Input:

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

Output:

3

(Giải thích: Dãy con chung tăng dài nhất là 1 2 5 hoặc 1 2 3).

Nhà An có N cái cây, cây thứ i có chiều cao ban đầu là A[i] cm. An vừa mua được M lọ thuốc tăng trưởng cực tốc. Mỗi lọ thuốc khi tưới vào một cái cây bất kỳ sẽ giúp cây đó cao thêm đúng 1 cm ngay lập tức (một cây có thể được tưới nhiều lọ thuốc).

An muốn sử dụng M lọ thuốc này một cách hợp lý nhất để chiều cao của cái cây thấp nhất trong vườn là cao nhất có thể.

Yêu cầu: Hãy tính chiều cao của cái cây thấp nhất sau khi An đã sử dụng tối ưu toàn bộ M lọ thuốc.

Dữ liệu vào: Đọc từ thiết bị chuẩn (bàn phím)

Dòng đầu tiên chứa hai số nguyên dương N và M (1 <= N <= 10^5, 0 <= M <= 10^9).

Dòng thứ hai chứa N số nguyên biểu diễn chiều cao ban đầu của các cây A[1], A[2], ..., A[N] (0 <= A[i] <= 10^9).

Dữ liệu ra: Ghi ra thiết bị chuẩn (màn hình)

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Giải thích ví dụ:

Có 3 cây với chiều cao lần lượt là 2, 4, 6. An có 4 lọ thuốc.

Phương án tối ưu:

Dùng 3 lọ thuốc cho cây thứ nhất: Chiều cao từ 2 -> 5.

Dùng 1 lọ thuốc cho cây thứ hai: Chiều cao từ 4 -> 5.

Cây thứ ba không dùng thuốc: Chiều cao giữ nguyên là 6.

Sau khi dùng hết 4 lọ thuốc, chiều cao của các cây là: 5, 5, 6. Cái cây thấp nhất trong vườn lúc này cao 5cm. Đây là kết quả tối ưu nhất.

Tìm giá trị trung bình lớn nhất của một mảng con liên tiếp có độ dài ít nhất là K.

Input:

• Dòng 1: N, K (1 ≤ K ≤ N ≤ 10^5).

• Dòng 2: A; (1 ≤ Ai ≤ 10^9).

Output: In ra kết quả làm tròn xuống (số nguyên lớn nhất ≤ giá trị thực).

Input:

5 2
1 10 10 1 1

Output:

10

Trạm radar đặt tại tọa độ (0, 0) có bán kính phủ sóng là R. Bạn hãy tính xem có bao nhiêu điểm có tọa độ nguyên (cả hoành độ và tung độ đều là số nguyên) nằm hoàn toàn bên trong hoặc nằm ngay trên đường ranh giới của vùng phủ sóng radar này.

Input: Một dòng chứa số nguyên dương R (1 <= R <= 10^6).

Output: Số lượng điểm nguyên thỏa mãn.

Ví dụ:

Input:

2

Output:

13

(Giải thích: Các điểm là (0,0), (0,1), (0,2), (0,-1), (0,-2), (1,0), (2,0), (-1,0), (-2,0), (1,1), (1,-1), (-1,1), (-1,-1)).

Một mỏ quặng có N đống khoáng sản, đống thứ i có khối lượng Wi kg và chứa tổng giá trị là Vi đồng. Chiếc xe lùi của bạn chỉ chở được tối đa M kg. Rất may, bạn có thể xúc một phần lẻ của một đống quặng (ví dụ lấy 0.5 kg). Hãy tìm cách xúc quặng lên xe sao cho tổng giá trị thu được là lớn nhất.

Input:

Dòng 1: N, M (1 <= N <= 10^5, 1 <= M <= 10^9).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Wi, Vi (1 <= Wi, Vi <= 10^5).

Output: Giá trị lớn nhất thu được, in ra phần nguyên (làm tròn xuống).

Ví dụ:

Input:

3 50
10 60
20 100
30 120

Output:

240

(Giải thích: Lấy toàn bộ đống 1 (10kg, 60đ), toàn bộ đống 2 (20kg, 100đ), và 20/30 đống 3 (20kg, 80đ). Tổng khối lượng 50kg, giá trị 240đ).

Kho hàng có N loại pin năng lượng. Loại pin thứ i có trọng lượng Wi, dung lượng điện Vi và bạn chỉ có số lượng tối đa là C_i viên pin loại này. Một robot thám hiểm cần nạp pin vào khoang chứa có tải trọng tối đa là M. Hãy tìm cách chọn các viên pin sao cho không vượt quá tải trọng M mà dung lượng điện nạp được là lớn nhất.

Input:

Dòng 1: N, M (1 <= N <= 100, 1 <= M <= 10^4).

N dòng tiếp theo: Mỗi dòng 3 số nguyên Wi, Vi, Ci (1 <= Wi, Vi <= 1000, 1 <= Ci <= 100).

Output: Tổng dung lượng điện lớn nhất.

Ví dụ:

Input:

2 10
3 4 2
4 5 3

Output:

13

(Giải thích: Chọn 2 viên loại 1 (nặng 6, điện 8) và 1 viên loại 2 (nặng 4, điện 5). Tổng nặng 10, điện 13).