Độ khó: Dễ (1/4 điểm)

Bé Sen đang học chuyên đề về các thuật toán số học và rất hào hứng với những thuật toán xử lí số. Hôm nay, bé Sen lại được biết thêm một thuật toán mới để biến đổi một số nguyên dương $n$ về giá trị $1$. Mỗi phép biến đổi số $n$ được thực hiện như sau:

• Nếu $n$ là số chẵn thì thay $n$ bằng giá trị $n / 2$;
• Nếu $n$ là số lẻ thì thay $n$ bằng giá trị $3n + 1$.

Yêu cầu: Với số nguyên dương $n$ cho trước, cần thực hiện bao nhiêu phép biến đổi để $n$ nhận giá trị bằng $1$?

Input

Một dòng chứa số nguyên dương $n$ ($1 \le n \le 1000$).

Output

Một dòng chứa một số nguyên duy nhất là số phép biến đổi để $n$ nhận giá trị bằng $1$.

Sample Input

13

Sample Output

9

Giải thích

$13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$.

Độ khó: Dễ (1/4 điểm)

Trong tiết học lập trình, sau khi được giáo viên hướng dẫn các phép toán chia hết và phép chia có dư, các em học sinh rất hào hứng và hoàn thành tốt các bài tập. Để tăng độ khó, giáo viên cho bài tập "Trong phạm vi không vượt quá số nguyên dương $n$, hãy cho biết có bao nhiêu số nguyên dương là bội của $3$ hoặc bội của $5$".

Yêu cầu: Cho trước số nguyên dương $n$, hãy cho biết có bao nhiêu số nguyên dương là bội của $3$ hoặc của $5$ mà không vượt quá $n$.

Input

Một dòng chứa số nguyên dương $n$ ($1 \le n \le 10^9$).

Output

Một dòng chứa một số nguyên duy nhất là kết quả.

Subtask

• 80% số test (80% số điểm): $1 \le n \le 10^6$.
• 20% số test (20% số điểm): $10^6 < n \le 10^9$.

Sample Input

16

Sample Output

7

Giải thích

Các số thỏa mãn: $3, 5, 6, 9, 10, 12, 15$.

Độ khó: Dễ (1/4 điểm)

Bạn An là một học sinh vô cùng xuất sắc. Hôm nay, An lại tiếp tục đứng nhất trong một kì thi lập trình trực tuyến, vì thế thầy chủ nhiệm quyết định tặng cho bạn ấy một số gói kẹo xem như phần thưởng. Có tất cả $n$ gói kẹo, mỗi gói chứa một số viên kẹo và thầy dự định tặng cho bạn An $k$ gói kẹo trong số $n$ gói kẹo đó. Mặt khác, vì là học sinh rất xuất sắc nên thầy muốn chọn các gói kẹo sao cho tổng số viên kẹo bạn An nhận được là nhiều nhất.

Yêu cầu: Hãy cho biết tổng số viên kẹo nhiều nhất mà bạn An nhận được là bao nhiêu?

Input

• Dòng thứ nhất ghi hai số nguyên dương $n$ và $k$ ($1 \le k \le n \le 10^5$).
• Dòng thứ hai ghi $n$ số nguyên dương $a1, a2, \ldots, an$ ($1 \le ai \le 10^6$), $a_i$ là số viên kẹo trong gói thứ $i$.

Output

Một dòng chứa một số nguyên duy nhất là tổng số viên kẹo nhiều nhất mà bạn An nhận được.

Subtask

• 80% số test (80% số điểm): $1 \le n \le 10^3$.
• 20% số test (20% số điểm): $10^3 < n \le 10^5$.

Sample Input

8 3
7 2 4 6 3 5 1 6

Sample Output

19

Giải thích

Chọn các gói có $7$, $6$, $6$ viên kẹo: $7 + 6 + 6 = 19$.

Độ khó: Trung bình (2/4 điểm)

Trong một khóa học lập trình trực tuyến có $n$ học viên tham gia. Sau thời gian luyện tập giải các bài tập, các học viên được đánh giá bằng chỉ số năng lực trên bảng xếp hạng, học viên thứ $i$ có chỉ số năng lực là $a_i$ ($i = 1 \ldots n$). Biết rằng, không có hai học viên nào có cùng chỉ số năng lực. Ban tổ chức khóa học dự định tổ chức cho các học viên chia thành các đội để lập trình thi đấu cùng nhau, mỗi đội gồm hai học viên sao cho tổng chỉ số năng lực của hai học viên trong một đội đúng bằng $k$.

Yêu cầu: Hãy cho biết ban tổ chức khóa học có thể chia được nhiều nhất thành bao nhiêu đội để tham gia thi đấu?

Input

• Dòng thứ nhất ghi hai số nguyên dương $n$, $k$ ($1 \le n \le 10^5$, $1 \le k \le 10^9$).
• Dòng thứ hai ghi $n$ số nguyên dương $a1, a2, \ldots, an$ ($1 \le ai \le 10^9$, $ai \ne aj$ với $i \ne j$).

Output

Một dòng chứa một số nguyên duy nhất là kết quả.

Subtask

• 40% số test (40% số điểm): $1 \le n \le 10^3$.
• 60% số test (60% số điểm): $10^3 < n \le 10^5$.

Sample Input

9 17
5 16 7 12 10 2 17 15 1

Sample Output

4

Giải thích

Các đội: $(5, 12)$, $(7, 10)$, $(2, 15)$, $(16, 1)$ - đều có tổng bằng $17$; học viên có chỉ số $17$ không có bạn cùng đội.