Thị xã Điện Bàn được coi là cái nôi của truyền thống hiếu học. Cậu bé Nam được sinh ra và lớn lên tại nơi đây. Em ấy rất tự hào về quê hương của mình. Nam nổi tiếng thông minh, học giỏi. Niềm đam mê của em là thích nghiên cứu, tìm tòi giải các bài toán khó. Chuyên đề “Số chính phương” trong tiết học tuần qua thầy giáo có nói:
Số chính phương là số tự nhiên có căn bậc hai là một số tự nhiên, hay nói cách khác, số chính phương bằng bình phương (lũy thừa bậc 2) của một số nguyên.

Ví dụ:

• \(1^2 =1\)
• \(2^2=4\)
• \(3^2=9\)
• ….

Để nắm vứng kiến thức, Nam được thầy giáo giao cho bài tập về nhà liên quan đến nội dung này. Yêu cầu cụ thể như sau:

Cho số nguyên dương \(N\ (N ≤ 10^7)\). Hãy đếm xem có bao nhiêu số chính phương trong phạm vi từ \(K\) đến \(N\ (1≤ K≤ N)\)

Input: từ file văn bản SQUARE.INP gồm một dòng chứa số \(N\) và \(K\) (Mỗi số cách nhau một khoảng trắng)

Output: từ file văn bản SQUARE.OUT gồm một số \(D\) là kết quả cần tìm.

Scoring

• Có 50% test tương ứng 50% số điểm của bài với \(1≤ N ≤ 10^4;1≤ K≤ N\).
• Có 50% test tương ứng 50% số điểm của bài với $10^4

Được biết, giải nhì là thành tích cao nhất của Lâm sau khi tham gia kỳ thi Tin học trẻ cấp tỉnh năm học 2021-2022. Vì thế, Lâm đã được bố mẹ dẫn đi tham quan khu du lịch Đại Nam thuộc tỉnh Bình Dương. Nơi đây có trò chơi “MONEY - BALL” hấp dẫn làm Lâm thích thú. Trong trò chơi này, người ta cho một dãy quả bóng tròn, mỗi quả bóng mang một ký tự chữ số hoặc ký tự chữ cái. Trò chơi yêu cầu loại bỏ một số quả bóng ra khỏi dãy sao cho \(K\) số lượng bóng cuối cùng theo đúng thứ tự vị trí đó tạo thành số lớn nhất. Con số này cũng chính là số tiền mà Lâm nhận được khi thắng cuộc trò chơi.

Sau khi nghe xong luật chơi, Lâm quyết tâm dành chiến thắng để có được tiền mua quà về cho em gái mình. Bạn nghĩ xem, với người giỏi lập trình như Lâm, em ấy sẽ làm cách nào để nhận được số tiền như mong đợi.

Input: File văn bản BIGNUM.INP gồm:

• Dòng thứ nhất là một xâu \(s\) cho trước, xâu chỉ chứa các ký tự số và chữ cái (bao gồm cả ký tự thường và ký tự hoa). (\(s\) không quá 106 ký tự)
• Dòng thứ 2 chứa số nguyên dương \(K\) (\(1≤\) số lượng số \(K≤ 10^6\))

Output: Ghi ra file văn bản BIGNUM.OUT gồm một dòng duy nhất chứa kết quả cần tìm.

Scoring

• Có 50% test tương ứng 50% số điểm của bài với \(1 ≤\) số lượng số \(K ≤ 20\), độ dài xâu \(st\) không quá \(255\) ký tự;
• Có 25% test tương ứng 25% số điểm của bài với \(1 ≤\) số lượng số \(K ≤ 10^3\), độ dài xâu \(st\) không quá \(10^3\) ký tự;
• Có 25% test tương ứng 25% số điểm của bài với \(1 ≤\) số lượng số \(K ≤ 10^6\), độ dài xâu \(st\) không quá \(10^6\) ký tự;

Example

A79C3e8
2

98

Tinhoc95Tre68nam2023
3

983

Thầy A nổi tiếng là thầy giáo dạy giỏi. Thầy rất được học sinh yêu quý. Năm học 2020-2021, thầy đã hứa với trò của mình rằng: “Bạn nào thi đỗ vào trường THPT chuyên Lê Thánh Tông hoặc Nguyễn Bỉnh Khiêm thì thầy sẽ tặng cho mỗi em một cuốn sách thuật toán & lập trình môn Tin học”.

Và đúng như lời thầy nói, sau khi biết được kết quả và số lượng thí sinh đỗ trường THPT chuyên, thầy A đã vội vã đi mua sách. Khi đến tại cửa hàng sách Fahasha, thầy được nhân viên giới thiệu là có \(N\) cuốn sách lập trình với nhiều ngôn ngữ khác nhau \((2 ≤ N ≤ 10^7)\), cuốn sách thứ \(i\ (1 ≤ i ≤ N)\) có giá \(a_i\) đồng \((1 ≤ a_i ≤ 10^{15})\). Thầy A muốn chọn mua \(M\) cuốn sách để tặng cho \(M\) bạn \((2 ≤ M ≤ N)\).

Với tình yêu thương học trò, để đảm bảo tính công bằng giữa các em, không để em nào chịu thiệt, thầy \(A\) muốn mua các cuốn sách sao cho giá tiền chênh lệch giữa các cuốn sách có giá tiền cao nhất và thấp nhất là nhỏ nhất có thể.

Input: Từ file văn bản CHOSEBOOK.INP gồm:

• Dòng 1: Chứa hai số nguyên dương \(N\) và \(M\) (các giá trị cách nhau một khoảng trắng);
• Dòng 2: Chứa \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) (các giá trị cách nhau một khoảng trắng)

Input: Ghi ra file CHOSEBOOK.OUT gồm một số \(K\) duy nhất là kết quả cần tìm.

Scoring
• Có 25% test tương ứng 25% số điểm của bài với \(N ≤ 15; M≤ 15; 1 ≤ a_i ≤ 100\);
• Có 25% test tương ứng 25% số điểm của bài với \(N ≤ 10^3; M≤ 10^3; 1 ≤ a_i ≤ 10^5\);
• Có 50% test tương ứng 50% số điểm của bài với \(N ≤ 10^7; M≤ 10^7; 1 ≤ a_i ≤ 10^{15}\);

Example

    5 3
    4 7 2 9 3

    2

Năm 2020, Công ty cổ phần liên doanh ô tô Hyundai Việt Nam đã xuất khẩu 5 lần, mỗi lần xuất đi với \(n\) chiếc xe ô tô bằng cách cho tàu thủy mang biển kiểm soát VN6789 vận chuyển qua đường biển.

Với mỗi chiếc ô tô thứ \(i\ (1 ≤ i ≤ n)\), có trọng lượng là \(K_i\ (1 ≤ Ki ≤ 10^9)\) và giá trị \(U_i\ (1 ≤ Ui ≤ 10^9)\). Công ty mong muốn xuất được nhiều xe nhưng tàu chỉ vận chuyển khối lượng hàng nằm trong quy định cho phép \(Q\ (1 ≤ Q ≤ 1000)\). Vì thế, công ty đã thử chọn phương án cho mỗi lần xuất khẩu là mỗi loại xe chỉ lấy đi một chiếc sao cho những chiếc xe đã xuất đi có tổng giá trị lớn nhất.

Kể từ những lần xuất khẩu của năm đó, lợi nhuận của công ty tăng lên vượt bậc. Dự kiến đến năm 2025, công ty cổ phần liên doanh ô tô Hyundai Việt Nam sẽ xuất khẩu ô tô thêm 5 lần nữa. Trong năm này, Giám đốc công ty đưa ra yêu cầu cho bộ phận kinh doanh phải tiếp tục hợp đồng với tàu chở hàng VN6789 để mỗi lần xuất khẩu, các xe sẽ chọn đi sao cho tổng giá trị năm 2025 phải cao hơn tổng giá trị các chiếc xe mỗi lần xuất đi năm 2020. Đồng thời, tính giá trị hao hụt qua các lần xuất khẩu giữa năm 2020 và 2025 là bao nhiêu? Biết rằng, phương án được chọn cho các chuyến đi năm 2025 là mỗi loại xe có thể chọn số lượng nhiều.

Yêu cầu: Để đáp ứng mong đợi của ban giám đốc, theo em bộ phận kinh phải làm thế nào để đưa ra giá trị hao hụt qua những lần xuất khẩu của năm 2020 so với 2025.
Input: Từ tệp văn bản BOATCAR.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(Q\) (các giá trị cách nhau một khoảng trắng)
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(K_i\) và \(U_i\) (các giá trị cách nhau một khoảng trắng).

Output: Ghi ra tệp văn bản BOATCAR.OUT gồm 3 dòng:

• Dòng thứ nhất chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2020.
• Dòng thứ hai chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2025.
• Dòng thứ ba chứa giá trị hao hụt các xe đã xuất khẩu trong năm 2020 so với năm 2025.

Scoring

• Có 40% test tương ứng 40% số điểm của bài với \(n ≤ 30;1 ≤ U_i ≤ 10^2;1 ≤ K_i ≤ 10^2\)
• Có 40% test tương ứng 40% số điểm của bài với $n <10^2;10^2 < U_i ≤ 10^6 ;10^2