Một quyển sách gồm N trang (N luôn là số chẵn), được đánh số từ 1 đến N. Trong đó, trang 1 luôn nằm phía bên phải của trang bìa đầu, trang N luôn nằm ở mặt bên trái của trang bìa cuối của quyển sách.

Hôm nay, giáo viên yêu cầu cả lớp lật đến trang P trong quyển sách, theo tiêu chí sau:

• Có thể bắt đầu lật từ trang đầu 1 hoặc trang cuối N.
• Mỗi lần chỉ lật một mặt trang. Ví dụ: Bắt đầu từ trang 1, sau khi lật một lần sẽ đến trang 2, 3; lật hai lần sẽ đến trang 4, 5... Tương tự như vậy, nếu bắt đầu từ trang N, sẽ dẫn đến các trang N-1, N-2, ...
• Số lần lật đến trang P là ít nhất.

Yêu cầu:

Viết chương trình trả về kết quả là số lần lật đến trang P (1 < P < N) trong quyển sách thỏa tiêu chí trên.

Dữ liệu:

Dòng duy nhất chứa hai số nguyên dương N, P (~N \leq 10^{18}~) nằm trên một dòng, cách nhau ít nhất một ký tự trắng.

Kết quả:

Ghi ra một số nguyên là kết quả tìm được.

Ví dụ:

Ràng buộc dữ liệu:

• 75% test ứng với: ~1 < P \leq 10^9~.
• 25% test ứng với: ~10^9 < N \leq 10^{18}~.

Mọi dữ liệu trong máy tính đều được số hóa, tức là có dạng dãy các bit 0 và 1. Mọi thao tác xử lý dữ liệu trên máy tính cuối cùng đều dẫn đến xử lý các bit. Vì vậy khi thực hiện xong một bài toán, máy tính phải giải mã kết quả từ hệ nhị phân sang hệ thập phân để con người có thể hiểu và kiểm tra được. Việc đổi số nhị phân có dạng dₖdₖ₋₁...d₀ sang số thập phân thực chất chỉ là việc tính tổng:

$$d_k \times 2^k + d_{k-1} \times 2^{k-1} + ... + d_1 \times 2^1 + d_0 \times 2^0$$

Ví dụ: Dãy bit 111 trong hệ nhị phân chuyển sang hệ thập phân sẽ là số 7, vì:
~111_2 = 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 7_{10}~
Hôm nay bạn hãy viết chương trình giải bài toán như sau:
Cho dãy bit của hai số nguyên dương a, b (~1 < a < b \leq 10^{18}~) trong hệ nhị phân.

Yêu cầu:

• Đếm số lượng số chính phương có trong đoạn từ a đến b.
• Biết rằng, một số nguyên dương được gọi là số chính phương nếu căn bậc hai của nó là một số nguyên dương.

Dữ liệu:

• Dòng thứ nhất là dãy bit của số nguyên dương a trong hệ nhị phân.
• Dòng thứ hai là dãy bit của số nguyên dương b trong hệ nhị phân.

Kết quả:

Ghi ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Ràng buộc dữ liệu:

✔ 75% test ứng với ~1 < a < b \leq 10^9~.
✔ 25% test ứng với ~10^9 < a < b \leq 10^{18}~.

Nhân dịp kết thúc năm học, Trường THCS ABC tổ chức cho các em học sinh giao lưu với nhau, có nhiều trò chơi được ban tổ chức đưa ra để các em cùng tham gia. Có N học sinh tham gia trò chơi, được xếp hàng thành một đường thẳng và được đánh số thứ tự từ 1 đến N (em thứ nhất được đánh số thứ tự là 1). Trong danh sách các em tham gia, số lượng bạn nam ít hơn khá nhiều so với số lượng bạn nữ. Vì thế, ban tổ chức đã không xếp 3 bạn nam cùng đứng kế nhau.

Yêu cầu:

Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên.

Dữ liệu:

• Một số nguyên dương N (~N \leq 64~).

Kết quả:

• Ghi ra một số nguyên là kết quả tìm được.

Ví dụ:

Ràng buộc dữ liệu:

✔ 25% test ứng với ~1 < N \leq 20~.
✔ 75% test ứng với ~20 < N \leq 64~.

Bốn năm cấp hai là khoảng thời gian ghi dấu nhiều kỉ niệm nhất của tuổi học trò, và những bức ảnh đẹp cũng thường từ đây mà xuất hiện. Trong 4 năm qua, Hoàng và các bạn cùng lớp 9A của mình đã có rất nhiều hình ảnh đáng nhớ! Mỗi loại bức ảnh đều có dung lượng và tính thẩm mỹ nhất định. Để lưu giữ lại những hình ảnh đẹp, Hoàng quyết định mua một chiếc thẻ nhớ ngoài dung lượng K (Gigabyte - GB) để lưu chúng.
Hoàng thấy việc này thật thú vị! Và muốn tạo một hoạt động vui nhộn cùng các bạn với nội dung như sau:

• Cho biết thông tin về số lượng các loại bức ảnh; mỗi loại sẽ có dung lượng và tính thẩm mỹ của loại đó.
• Câu hỏi của Hoàng là:
  "Hãy chọn các bức ảnh của từng loại để lưu vào thẻ nhớ mà mình đã mua sao cho tổng tính thẩm mỹ thu được là lớn nhất".
  Biết rằng một loại ảnh có thể không được chọn hoặc chọn với số lượng không hạn chế.

Yêu cầu:

Cho biết tổng giá trị lớn nhất của tính thẩm mỹ thu được khi trả lời câu hỏi của Hoàng là bao nhiêu?

Dữ liệu:

• Dòng thứ nhất chứa hai số N (~2 \leq N \leq 1000~) và K (~1 \leq K \leq 4~).
  
  • Trong đó N là số lượng các loại ảnh của Hoàng được đánh số thứ tự từ 1 đến N.
  • K là dung lượng thẻ nhớ Hoàng đã mua (tính bằng đơn vị GB).
• Trong N dòng tiếp theo, dòng thứ i chứa 2 số nguyên dương ai (~1 \leq a_i \leq 1024~), bi (~1 \leq b_i \leq 10^9~).
  
  • Trong đó ai là dung lượng của bức ảnh loại i theo đơn vị MB.
  • bi là giá trị tính thẩm mỹ của bức ảnh loại i (~1 \leq i \leq N~).

Ghi chú: 1GB = 1024MB

Kết quả:

Ghi ra một số nguyên là kết quả tìm được.

Ví dụ:

Ràng buộc dữ liệu:

✔ 50% test ứng với ~2 \leq N \leq 500~, ~K \leq 2~, ~a_i \leq 1024~, ~b_i \leq 32000~.
✔ 50% test ứng với ~500 < N \leq 1000~, ~K \leq 4~, ~a_i \leq 1024~, ~b_i \leq 10^9~.