Trong một trò chơi thực tế ảo, bạn đang điều khiển robot thu thập các khối năng lượng dọc theo một hành lang tuyến tính. Mỗi khối năng lượng có mức phát xạ là một số nguyên. Để tay trần của robot không bị quá tải, hệ thống yêu cầu bạn chỉ được nhặt một chuỗi các khối năng lượng liên tiếp sao cho không có hai khối nào kề nhau cùng mang năng lượng âm (số lẻ) hoặc cùng mang năng lượng dương (số chẵn). Hãy tính xem robot có thu thập được chuỗi năng lượng dài nhất là bao nhiêu khối?

Input:

Dòng 1: Chứa số nguyên N (1 <= N <= 10^5).

Dòng 2: Chứa N số nguyên A1, A2, ..., AN là mức phát xạ của các khối (1 <= Ai <= 10^9).

Output: In ra một số nguyên duy nhất là số lượng khối năng lượng nhiều nhất trong chuỗi an toàn.

Ví dụ:

Input:

5
1 2 4 5 7

Output:

2

Một điệp viên đang gửi tin nhắn mật về căn cứ bằng các tín hiệu vô tuyến. Tín hiệu này chỉ gồm các chữ cái in thường. Để tránh bị đối phương đánh cắp và tiết kiệm băng thông, hệ thống truyền tin tự động gộp các tín hiệu giống nhau phát ra liên tiếp thành một tín hiệu kèm theo số lần phát (nếu phát trên 1 lần). Hãy viết chương trình mô phỏng hệ thống này giúp căn cứ.

Input: Một dòng duy nhất chứa xâu S (Độ dài xâu không vượt quá 10^5).

Output: In ra xâu sau khi đã được rút gọn.

Ví dụ:

Input:

aaabbccccd

Output:

a3b2c4d

Liên minh ngân hà đang chế tạo một trạm vũ trụ mới. Họ có N cột trụ bằng thép Titanium với chiều dài khác nhau. Để tạo phần khung chịu lực hoàn hảo, kỹ sư trưởng cần cắt các cột trụ này để lấy ra ít nhất K thanh thép có chiều dài hoàn toàn bằng nhau. Tất nhiên, phần thép thừa sẽ bị loại bỏ và không thể ghép nối lại với nhau. Hãy tính xem chiều dài lớn nhất của thanh thép có thể tạo ra là bao nhiêu để tối ưu hóa không gian của trạm?

Input:

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

Dòng 2: N số nguyên Li là chiều dài của các cột trụ ban đầu (1 <= Li <= 10^9).

Output: Chiều dài lớn nhất có thể đạt được. Nếu không thể cắt được, in ra 0.

Ví dụ:

Input:

4 11
802 743 457 539

Output:

200

Một nhà khảo cổ phát hiện ra một hang động chứa N cổ vật cổ xưa. Cổ vật thứ i có trọng lượng là Wi và được định giá trị là Vi. Hang động đang có dấu hiệu sụp đổ, và chiếc drone vận chuyển của nhà khảo cổ chỉ có thể chở được tải trọng tối đa là M. Thời gian rất gấp rút, mỗi cổ vật chỉ có thể được bốc lên 1 lần hoặc bỏ lại. Hãy giúp nhà khảo cổ lựa chọn các cổ vật mang về sao cho tổng giá trị là lớn nhất.

Input:

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

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

Output: Tổng giá trị lớn nhất mang về được.

Ví dụ:

Input:

3 50
10 60
20 100
30 120

Output:

220