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

Gia đình Phúc vừa lắp đặt một hệ thống khóa cửa thông minh cho ngôi nhà mới. Để đảm bảo an toàn, hệ thống khóa yêu cầu tạo một mật mã mở cửa là chuỗi các chữ số. Phúc đề xuất tạo ra một mật mã đặc biệt dựa vào thông tin tổng hợp từ bố và mẹ. Theo đó, mỗi người chọn ra bộ ba số nguyên dương, Phúc sẽ tạo mật mã mở cửa là số nguyên dương nhỏ nhất vừa chia hết cho tổng bộ số của bố và tổng bộ số của mẹ.

Yêu cầu

Hãy viết chương trình giúp Phúc tạo được mật mã mở cửa như mong muốn.

Input

• Dòng 1 chứa bộ ba số nguyên dương mẹ chọn, cách nhau một dấu cách trống.
• Dòng 2 chứa bộ ba số nguyên dương bố chọn, cách nhau một dấu cách trống.

Output

Một dòng chứa mật mã mở cửa.

Ràng buộc

• Có 50% số test ứng với bộ ba số của bố và mẹ thỏa mãn: ~0 < \text{mỗi số} \le 10^6~.
• Có 50% số test ứng với bộ ba số của bố và mẹ thỏa mãn: ~10^6 < \text{mỗi số} \le 10^9~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

200 300 600
110 220 330

Sample Output

3300

Giải thích

Tổng bộ ba số của mẹ là: ~200 + 300 + 600 = 1100~. Tổng bộ ba số của bố là: ~110 + 220 + 330 = 660~. Số nguyên dương nhỏ nhất vừa chia hết cho ~1100~ và ~660~ là ~3300~. Mật mã mở cửa được lựa chọn là: ~3300~.

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

Cả thế giới đang hào hứng chờ đợi World Cup 2026 sắp diễn ra tại Mỹ, Canada và Mexico. Trong suốt vòng loại trước đó, để phân tích phong độ các đội tuyển, Liên đoàn bóng đá thế giới (FIFA) đã ghi nhận lịch sử kết quả thi đấu của các đội trong một khoảng thời gian dài. Lịch sử kết quả thi đấu của một đội tuyển được biểu diễn bằng xâu các ký tự đại diện liên tiếp, trong đó kết quả mỗi trận đấu được biểu diễn bằng một ký tự:

• W (Win): một trận thắng.
• D (Draw): một trận hòa.
• L (Loss): một trận thua.

Các đội bóng thường có các mạch trận liên tiếp có cùng kết quả: mạch trận thắng (...WWWW...), mạch trận hòa (...DDD...), hoặc mạch trận thua (...LLLLL...). Các mạch trận này được gọi là các chuỗi "phong độ đồng nhất". FIFA muốn phân tích dữ liệu tất cả các đội tuyển để tìm ra chuỗi kỷ lục "phong độ đồng nhất" dài nhất trong lịch sử thi đấu từ tất cả các đội tuyển.

Yêu cầu

Hãy viết chương trình tìm ra độ dài của chuỗi kỷ lục "phong độ đồng nhất" dài nhất từ lịch sử thi đấu của tất cả các đội tuyển.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ là số lượng đội tuyển được FIFA thống kê lịch sử kết quả thi đấu (~0 < n \le 100~).
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu các ký tự chữ cái in hoa liên tiếp thuộc tập {W, D, L}, tương ứng với dữ liệu kết quả thi đấu của một đội tuyển.

Output

Một số nguyên duy nhất là số trận trong chuỗi kỷ lục "phong độ đồng nhất" dài nhất lịch sử thi đấu từ tất cả các đội tuyển.

Ràng buộc

• Có 80% số test ứng với ~0 < n \le 10~ và độ dài xâu ~\le 100~.
• Có 20% số test còn lại ứng với ~10 < n \le 100~ và ~100 <~ độ dài xâu ~\le 10^4~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

3
WWWDLWW
LLLLLLWD
WDDL

Sample Output

6

Giải thích

Đội tuyển thứ nhất có chuỗi "phong độ đồng nhất" dài nhất là 3 (WWW: 3 trận thắng liên tiếp). Đội tuyển thứ hai có chuỗi "phong độ đồng nhất" dài nhất là 6 (LLLLLL: 6 trận thua liên tiếp). Đội tuyển thứ ba có chuỗi "phong độ đồng nhất" dài nhất là 2 (DD: 2 trận hòa liên tiếp). Vậy chuỗi kỷ lục "phong độ đồng nhất" dài nhất là 6.

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

Muốn chọn một số vị trí trên tuyến đường để đặt trạm sạc xe điện, công ty XNOVA tiến hành chia tuyến đường thành ~n~ vị trí liên tiếp, đánh số từ ~1~ đến ~n~. Kết quả khảo sát cho thấy, lượng xe có nhu cầu sạc mỗi ngày ở vị trí thứ ~i~ (~1 \le i \le n~) là ~a_i~.

Để tránh quá tải hệ thống điện, công ty sẽ không đặt trạm sạc ở tất cả ~n~ vị trí khảo sát. Phương án đặt trạm sẽ theo nguyên tắc: trạm sạc đặt tại vị trí khảo sát thứ ~i~ sẽ phục vụ tối đa ~a_i~ lượt xe mỗi ngày và không đặt trạm tiếp theo trong phạm vi ~L~ vị trí liền sau nó. Cụ thể, nếu hai trạm đặt tại các vị trí khảo sát ~i~ và ~j~ (với ~i < j~) thì phải thỏa mãn ~j - i > L~.

Với phạm vi ~L~ cho trước, công ty muốn tìm phương án đặt trạm sạc tối ưu để tổng số lượt xe tối đa có thể phục vụ mỗi ngày là lớn nhất.

Input

• Dòng đầu tiên ghi hai số nguyên ~n~ và ~L~ cách nhau một dấu cách (~1 \le n \le 10^6~, ~0 \le L < n~).
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ cách nhau một dấu cách (~0 \le a_i \le 10^9~).

Output

Ghi ra một số nguyên duy nhất là tổng số lượt xe lớn nhất có thể phục vụ mỗi ngày.

Subtask

• Subtask 1 (50% số điểm): ~1 \le n \le 25~, ~0 \le L < n~.
• Subtask 2 (30% số điểm): ~1 \le n \le 10^5~, ~L = 1~.
• Subtask 3 (20% số điểm): ~1 \le n \le 10^6~, ~0 \le L < n~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

7 1
6 10 3 8 5 9 4

Sample Output

27

Giải thích

Vì phạm vi ràng buộc ~L = 1~, nên nếu đặt trạm sạc tại vị trí khảo sát ~i~ thì không được đặt thêm trạm sạc tại vị trí khảo sát liền sau nó (~i + 1~). Phương án hợp lệ tối ưu là đặt trạm tại các vị trí khảo sát ~2, 4, 6~. Khi đó tổng số lượt xe tối đa có thể phục vụ là lớn nhất: ~10 + 8 + 9 = 27~. Không có cách chọn hợp lệ nào khác cho tổng lớn hơn ~27~.

Độ khó: Khá (3/4 điểm)

Để chuẩn bị cho giải đấu Robot toàn quốc, đội của Thư dự định mua một số Robot từ doanh nghiệp XBOT. Doanh nghiệp này trưng bày một dãy Robot được đánh số từ ~1~ đến ~n~ (từ trái qua phải). Robot thứ ~i~ được dán nhãn mức tiêu thụ năng lượng ~p_i~ và có năng lực thi đấu ~w_i~.

Đội của Thư nhờ chuyên gia chọn lần lượt từ trái qua phải một hoặc nhiều Robot thỏa mãn điều kiện: Robot chọn sau phải có nhãn mức tiêu thụ năng lượng lớn hơn Robot chọn trước (~p_i < p_j~ với ~i < j~) và tổng năng lực thi đấu của các Robot được chọn là lớn nhất.

Yêu cầu

Hãy viết chương trình giúp chuyên gia tìm ra phương án chọn Robot thỏa mãn điều kiện đặt ra sao cho tổng năng lực thi đấu là lớn nhất.

Input

• Dòng 1: Số nguyên dương ~n~ (~n \le 5 \cdot 10^5~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ (~i = 1 \ldots n~) có hai số nguyên dương ~p_i~ (~p_i \le 10^9~) và ~w_i~ (~w_i \le 10^6~) tương ứng là nhãn mức tiêu thụ năng lượng và năng lực thi đấu của Robot thứ ~i~, mỗi số cách nhau một dấu cách trống.

Output

Ghi ra một số nguyên duy nhất là tổng năng lực thi đấu lớn nhất của các Robot được chọn.

Subtask

• Subtask 1 (50% số điểm): ~n \le 10^3~.
• Subtask 2 (50% số điểm): ~10^3 < n \le 5 \cdot 10^5~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5
5 16
3 6
4 5
5 2
2 8

Sample Output 1

16

Giải thích 1

Chọn Robot thứ nhất, tổng năng lực thi đấu là 16.

Sample Input 2

5
4 10
1 3
5 15
3 10
4 12

Sample Output 2

25

Giải thích 2

Có thể chọn các Robot thứ 1, 3 để có tổng năng lực thi đấu là: ~10 + 15 = 25~. Hoặc có thể chọn các Robot thứ 2, 4, 5 để có tổng năng lực thi đấu là: ~3 + 10 + 12 = 25~. Kết quả in ra là 25.