Thi thử đợt 2 tuyển sinh lớp 10 Chuyên KHTN 2026

Kem và cá sấu Kẹp quyết định đi du lịch. Chúng đi bộ và mang chung một chiếc vali. Chúng quyết định một trong hai cầm vali, và người còn lại sẽ cõng người kia cùng với chiếc vali này.

Được biết, trọng lượng của Kem là \(A\) kg và cậu có thể mang \(B\) kg, trọng lượng của cá sấu Kẹp là \(C\) kg và cậu có thể mang \(D\) kg. Trọng lượng của vali chứa đồ là \(Z\) kg.

Trước khi bắt đầu cuộc hành trình, họ có thể vứt bỏ một phần hàng hóa có khối lượng bất kỳ khỏi vali. Họ có thể mang đi khối lượng hàng hóa lớn nhất là bao nhiêu theo cách này? Trọng lượng của một chiếc vali rỗng nên được bỏ qua.

Input

• Dữ liệu nhập vào gồm năm dòng, mỗi dòng ghi một số tự nhiên lần lượt là \(A, B, C, D\) và \(Z\).

Output

• In ra khối lượng hàng hóa tối đa trong vali mà Kem và Kẹp có thể mang theo, với điều kiện họ đi du lịch theo cách được mô tả ở trên. Nếu không ai trong số họ có thể mang người kia đi, tức là không thể đi du lịch, in ra \(-1\).

Constraints

• \(A, B, C, D, Z \le 10^{18}\).
• 12% số test có \(Z = 1\).
• 12% số test có \(A + B = C + D\).

Example

50
30
100
70
80

20

70
30
100
70
80

0

110
30
100
70
80

-1

Một thành phố tổ chức đại hội ba đảng, với số lượng đại biểu lần lượt là \(a, b\) và \(c\) từ đảng A, đảng B và đảng C. Tất cả các đại biểu đều muốn ở lại khách sạn tốt nhất "California", và vì tổng số người đến là \(3 \cdot n\), giám đốc khách sạn quyết định cung cấp \(n\) phòng \(3\) người.

Nhân viên lễ tân (một người ủng hộ bí mật của đảng A) có thể sắp xếp khách theo ý mình. Cậu biết rằng nếu có \(2\) đảng viên của một đảng và một người từ một đảng khác ở chung một phòng, thì hai người cùng đảng sẽ thuyết phục được người thứ ba gia nhập đảng của họ.

Tính số lượng thành viên lớn nhất của đảng A có thể có trong khách sạn sau khi sắp xếp như vậy.

Input

• Ba dòng đầu vào chứa ba số nguyên không âm: \(a, b\) và \(c\) (\(0 \le a, b, c \le 10^8, a + b + c \ge 3\)). Đảm bảo tổng của chúng chia hết cho \(3\).

Output

• In ra một số nguyên không âm duy nhất là số lượng thành viên lớn nhất của đảng A.

Example

3
2
1

4

Scoring

• 40% số test có \(a < b\) và \(c = 0\).
• 60% số test còn lại không có ràng buộc gì thêm.

Một chuỗi con được gọi là khác biệt nếu mỗi chữ cái trong đó xuất hiện không quá một lần. Kem thích chơi với các từ theo cách sau: Cậu lấy một từ và tách nó thành các chuỗi con khác biệt.

Ví dụ: từ abba có thể được tách thành các chuỗi con khác biệt theo \(4\) cách:

• a b b a
• ab b a
• a b ba
• ab ba

Tuy nhiên, Kem không phải lúc nào cũng có thể tách từ đúng. Hãy giúp cậu đếm tất cả các cách chia từ \(s\) thành các chuỗi con khác biệt. Các chuỗi con trong cách tách không được để trống.

In số cách tách thỏa mãn (theo modulo \(998244853\)).

Input

• Dòng đầu ghi từ \(s\). (Từ \(s\) chỉ chứa các chữ cái tiếng Anh in thường, \(|s| \le 10^5\)).

Output

• In ra số cách tách một từ thành các chuỗi con khác biệt theo modulo \(998244853\).

Example

abcbca

20

abba

4

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(|s| \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(|s| \le 10^5\).

Nhập vào số nguyên dương \(n≤10^{14}\), liệt kê các ước số dương của \(n\) theo thứ tự tăng dần.

Input

• Vào từ thiết bị nhập chuẩn số nguyên dương \(n\).

Output

• Ghi ra thiết bị xuất chuẩn các ước số dương của \(n\) theo thứ tự tăng dần, mỗi ước số trên một dòng.

Example

10

1
2
5
10

Cho dãy số nguyên dương \(a\) gồm \(n\) số phân biệt \(a_1, a_2, \dots, a_n\). Cho \(q\) truy vấn, mỗi truy vấn gồm hai chỉ số \(i\) và \(j\).

In ra độ dài cấp số cộng dài nhất của dãy \(a\) mà chứa \(a_i\) và \(a_j\). Các phần tử của cấp số cộng là các phần tử của dãy \(a\), không quan tâm đến vị trí trong \(a\).

Ví dụ: nếu \(a = [2, 6, 5, 1, 4, 8]\), \((i, j) = (1, 5)\) thì \(a_i = 2, a_j = 4\), đáp án là \(4\) (cấp số cộng: \(2, 4, 6, 8\)).

Input

• Dòng đầu ghi hai số \(n, q\) (\(1 \le n \le 1000, 1 \le q \le 10^6\)).
• Dòng thứ hai ghi \(n\) số \(a_i\) (\(1 \le a_i \le 2000\)).
• Mỗi dòng trong \(q\) dòng tiếp theo ghi hai chỉ số \(i\) và \(j\) (\(1 \le i < j \le n\)).

Output

• In ra \(q\) dòng, mỗi dòng là kết quả của từng truy vấn.

Constraints

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 1000, q \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc bổ sung.

Example

6 7
2 6 5 1 4 8
1 5
1 4
2 3
2 5
4 6
3 4
1 6

4
2
3
4
2
2
4

Kem đi học về và nhận ra mình quên mua kem. Cậu phải thật khẩn trương: một trận đấu bóng yêu thích của cậu sẽ được phát sóng trên TV trong \(n\) phút nữa.

Quãng đường từ nhà Kem đến tiệm kem mất \(t\) phút, và quãng đường về cũng mất chừng đó thời gian. Việc mua kem sẽ mất một phút. Đảm bảo \(2 \cdot t + 1 \leq n\).

Kem định đi mua kem, nhưng trời bắt đầu mưa phùn. Theo dự báo thời tiết, mưa sẽ rơi trong \(n\) phút tiếp theo, và cứ mỗi phút thứ \(j\), lượng mưa \(d_j\) sẽ rơi trong phút đó.

Kem muốn tổng lượng mưa rơi trong khi cậu đang đi bộ trên đường càng ít càng tốt. Kem có thể trì hoãn việc rời nhà, đợi một chút ở tiệm kem, hoặc không rời đi ngay sau khi mua kem. Điều quan trọng là cậu phải về nhà không muộn hơn \(n\) phút. Nhiệm vụ của bạn là xác định tổng lượng mưa tối thiểu có thể rơi trong khi Kem ở ngoài trời.

Input

• Dòng đầu tiên ghi số nguyên \(n\) (\(3 \leq n \leq 10^5\)) — thời gian tối đa mà Kem phải về nhà.
• Dòng thứ hai ghi số nguyên \(t\) (\(1 \leq t, 2t + 1 \leq n\)) — thời gian Kem đi bộ từ nhà đến tiệm kem và quay lại.
• Mỗi dòng trong \(n\) dòng tiếp theo chứa một số nguyên \(d_j\) (\(1 \leq d_j \leq 10^3, j = 1, 2, \dots, n\)) — lượng mưa sẽ rơi trong phút thứ \(j\).

Output

• In ra lượng mưa tối thiểu rơi xuống trong khi Kem đang đi bộ trên đường.

Example

18
4
5
2
1
4
2
1
11
3
2
1
14
12
3
1
2
1
6
2

15