2026 · HSG THPT · Đồng Nai

Một số tự nhiên ~N~ được xem là số may mắn nếu chữ số hàng đơn vị của nó là số ~9~.

Yêu cầu: Kiểm tra xem số tự nhiên ~N~ có phải là số may mắn hay không?

Input

Vào từ file văn bản SOMM.INP:

• Gồm một số nguyên ~N~ với giới hạn ~1 \leq N \leq 10^6~.

Output

Ghi ra file văn bản SOMM.OUT:

• Ghi số ~1~ nếu ~N~ là số may mắn, ngược lại ghi số ~0~.

Example input 1

2029

Example output 1

1

Example input 2

2026

Example output 2

0

Trong hội trại ~26~ tháng ~03~ thường niên năm ~2026~, ban tổ chức có tổ chức trò chơi lớn, các đội tham gia đều phải làm nhiệm vụ giải mật thư. Mỗi đội được phát cho một xâu kí tự gồm các kí tự số và chữ cái trong bảng chữ cái tiếng Anh có độ dài không quá ~100~ kí tự.

Từ xâu kí tự đã cho, mỗi đội phải tìm ra được khóa của xâu. Khóa của xâu là một số nguyên dương ~K~ được tìm bằng cách cộng các số (mỗi số có giá trị nhỏ hơn ~10000~) trong xâu đã cho.

Yêu cầu: Hãy xác định giá trị ~K~ là tổng các số có trong xâu.

Input

Vào từ file văn bản HOITRAI.INP:

• Gồm một xâu kí tự S.

Output

Ghi ra file văn bản HOITRAI.OUT:

• Ghi ra số nguyên dương ~K~ tìm được.

Example input 1

Lop10thihocsinhgioidatgiai2captinh

Example output 1

12

Note 1

• Trong ví dụ, các số trong xâu là ~10~ và ~2~, nên ~K = 10 + 2 = 12~.

Sau khi cơn lũ đi qua, có ~N~ ngôi nhà đánh số từ ~1~ đến ~N~ cần được cứu trợ; ngôi nhà thứ ~i~ cần ~A_i~ gói hàng cứu trợ. Chính quyền xã huy động được tối đa ~M~ thiết bị bay không người lái, mỗi thiết bị bay có cùng một tải trọng.

Tuy nhiên do điều kiện địa hình nên có một số ngôi nhà mà thiết bị bay không thể tiếp cận. Khả năng tiếp cận ngôi nhà thứ ~i~ là ~B_i~, trong đó:

• ~B_i = 1~ nếu thiết bị bay có thể tiếp cận ngôi nhà để thả hàng,
• ngược lại thì ~B_i = 0~.

Một thiết bị bay chở tối đa ~K~ gói hàng sẽ giao cho dãy các ngôi nhà liên tục, nhưng nếu gặp ngôi nhà không thể tiếp cận thì sẽ quay trở về để thiết bị bay khác tiếp tục. Mỗi thiết bị chỉ bay đúng ~1~ lần.

Yêu cầu: Hãy xác định giá trị ~K~ nhỏ nhất sao cho có thể giao đủ hàng cho tất cả các ngôi nhà có thể tiếp cận mà không sử dụng quá ~M~ thiết bị bay.

Input

Vào từ file văn bản DRONE.INP gồm ~3~ dòng:

• Dòng ~1~: hai số nguyên dương ~N~, ~M~ với giới hạn ~1 \leq M \leq N \leq 10^4~.
• Dòng ~2~: ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ với giới hạn ~1 \leq A_i \leq 10^6~.
• Dòng ~3~: ~N~ số nguyên ~B_1, B_2, \ldots, B_N~ với ~B_i \in \{0,1\}~.

Output

Ghi ra file văn bản DRONE.OUT:

• Ghi giá trị ~K~ nhỏ nhất tìm được. Trường hợp không đủ thiết bị bay hoặc tất cả các ngôi nhà đều không thể tiếp cận thì ghi ~-1~.

Scoring

• Subtask ~1~: ~M = N~
• Subtask ~2~: ~1 \leq M, N \leq 100~ và ~B_i = 1~
• Subtask ~3~: Không ràng buộc gì thêm

Example input 1

5 5
1 3 5 2 4
1 1 1 1 1

Example output 1

5

Note 1

• Mỗi thiết bị bay sẽ giao hàng cho ~1~ nhà.

Example input 2

7 3
3 4 2 5 1 3 2
1 1 1 1 1 1 1

Example output 2

7

Note 2

• Có thể chia thành ~3~ lượt giao liên tiếp: nhà ~1~-~2~, nhà ~3~-~4~, nhà ~5~-~7~.

Example input 3

7 3
3 4 2 5 1 3 2
1 0 1 0 1 0 1

Example output 3

-1

Note 3

• Có ~4~ nhà cần hàng cứu trợ mà chỉ có ~3~ thiết bị bay.

Trong giờ học toán tại lớp, cô giáo muốn kiểm tra các bạn ai nhanh trí hơn và tính toán nhanh hơn. Cô cho các bạn hai số nguyên dương ~N~ và ~M~, các bạn có nhiệm vụ tìm tất cả các số nguyên tố từ ~N~ đến ~M~. Sau đó cộng tất cả các chữ số của các số nguyên tố đó lại. Bạn nào làm nhanh và chính xác nhất cô sẽ tặng cho một bông hoa điểm ~10~.

Yêu cầu: Hãy tính tổng các chữ số của các số nguyên tố tìm được từ ~N~ đến ~M~.

Input

Vào từ file văn bản NGUYENTO.INP:

• Gồm hai số nguyên dương ~N~, ~M~ với giới hạn ~1 \leq N < M \leq 10^5~.

Output

Ghi ra file văn bản NGUYENTO.OUT:

• Tổng các chữ số của tất cả các số nguyên tố tìm được.

Scoring

• Subtask ~1~: ~1 \leq N < M \leq 10^3~
• Subtask ~2~: Không ràng buộc gì thêm

Example input 1

3 20

Example output 1

39

Note 1

• Các số nguyên tố: ~3~, ~5~, ~7~, ~11~, ~13~, ~17~, ~19~.
• Tổng chữ số: ~3 + 5 + 7 + (1+1) + (1+3) + (1+7) + (1+9) = 39~.

Có ~N~ viên gạch vuông bằng nhau xếp sát nhau thành một hàng dài trên mặt phẳng. Trên viên gạch thứ ~i~ có ghi một giá trị ~A_i~. Một robot được đặt ở trên viên gạch thứ ~1~ và robot sẽ nhảy đến viên gạch cuối cùng (viên gạch thứ ~N~).

Robot chỉ nhảy theo chiều tăng chỉ số. Do hạn chế về kỹ thuật và năng lượng, bước nhảy tiếp theo không thể dài hơn bước vừa nhảy ngay trước đó. Cụ thể, nếu robot đang ở viên gạch thứ ~i~ nhảy tới viên gạch thứ ~j~, sau đó từ viên gạch thứ ~j~ nhảy tới viên gạch thứ ~k~ thì phải thỏa:

• ~k - j \leq j - i~.

Yêu cầu: Hãy tìm tổng giá trị lớn nhất trên các viên gạch mà robot nhảy tới (tính cả viên bắt đầu và viên kết thúc).

Input

Vào từ file văn bản ROBOT.INP gồm ~2~ dòng:

• Dòng ~1~: số nguyên dương ~N~ với giới hạn ~1 \leq N \leq 10^4~.
• Dòng ~2~: ~N~ giá trị ~A_1, A_2, \ldots, A_N~ với giới hạn ~-10^9 \leq A_i \leq 10^9~.

Output

Ghi ra file văn bản ROBOT.OUT:

• Tổng giá trị lớn nhất trên các viên gạch mà robot nhảy tới.

Scoring

• Subtask ~1~: ~1 \leq N \leq 20~
• Subtask ~2~: ~20 \leq N \leq 500~
• Subtask ~3~: Không ràng buộc gì thêm

Example input 1

6
1 -1 5 -2 -1 2

Example output 1

7

Note 1

• Một cách nhảy đạt tổng ~7~: robot thăm các viên có giá trị ~1~, ~5~, ~-1~, ~2~ (tổng ~1 + 5 - 1 + 2 = 7~).