1 THT C2 2026

Một cửa hàng chuyên cung cấp Pin cho khách hàng theo hai hình thức:

• Một là khách hàng có thể mua một viên pin sử dụng một lần với giá \(a\) đồng.
• Hai là khách hàng có thể mua một viên pin đã sạc đầy có thể tái sử dụng với giá \(b\) đồng, đồng thời sau khi sử dụng hết nếu mang Pin cũ quay lại cửa hàng thì sẽ được hoàn lại \(c\) đồng.

Tom có \(n\) đồng và muốn mua được nhiều viên Pin nhất có thể. Hãy xác định số viên Pin tối đa mà Tom có thể mua được.

Input

• Một dòng duy nhất chứa bốn số nguyên \(n, a, b, c\) (\(1 \le n, a \le 10^{15}, 1 \le c < b \le 10^{15}\)).

Output

• Ghi ra một số nguyên duy nhất là số viên Pin tối đa mà Tom có thể mua được.

Example

10 11 9 8

2

Scoring

• Có \(80\%\) số test tương ứng với \(80\%\) số điểm có \(b - c \ge a\).
• Có \(20\%\) số test còn lại không có giới hạn gì thêm.

Trên một bàn cờ \(M \cdot N\) ô được bố trí \(K\) quân xe. Quân xe có thể tấn công tất cả các quân cờ nằm trên hàng và cột tại vị trí nó đang đứng. Các quân xe được bố trí tại các vị trí đảm bảo không có quân xe nào có thể tấn công lẫn nhau. Bạn cần xác định diện tích hình chữ nhật lớn nhất có thể để xây dựng thành trì sao cho tất cả các ô của thành trì đều ở vị trí an toàn. Một ô được gọi là an toàn nếu nó không bị bất kỳ quân xe nào tấn công.

Input

• Dòng đầu chứa ba số nguyên dương \(M, N, K\) (\(1 < M, N \le 10^9 , 1 \le K \le 10^6\)).
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x, y\) lần lượt là tọa độ của các quân xe trên bàn cờ (\(1 \le x \le M; 1 \le y \le N\)).

Output

• Ghi ra một số nguyên duy nhất là diện tích lớn nhất của thành trì an toàn.

Example

11 7 3
2 2
5 7
8 5

6

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(1 < K \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Một buổi sáng đẹp trời, Nam dạo bước trên con đường quen thuộc trong khu phố của mình. Con đường có \(N\) ngôi nhà được đánh số từ \(1\) đến \(N\). Mỗi ngôi nhà thứ \(i\) mang một giá trị \(A_i\) thể hiện mức độ "chuẩn" của ngôi nhà đó đối với vẻ đẹp chung của khu phố. Trong lúc tản bộ, Nam nảy ra một ý tưởng thú vị: Nam chọn ra các đoạn ngôi nhà liên tiếp sao cho tổng mức độ "chuẩn" của chúng không nhỏ hơn một ngưỡng \(S\), Nam gọi những đoạn như vậy là dãy nhà đạt chuẩn. Cụ thể, một đoạn các ngôi nhà liên tiếp từ \(L\) đến \(R\) (\(1 \le L \le R \le N\)) được gọi là dãy nhà đạt chuẩn nếu: \(A_L + A_{L+1} + \dots + A_R \ge S\).

Yêu cầu: Trong số các dãy nhà đạt chuẩn mà Nam đã chọn, hãy xác định độ dài \(K\) nhỏ nhất của một dãy nhà đạt chuẩn. Nếu không tồn tại dãy nào thỏa mãn thì in ra \(0\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N, S\) (\(1 \le N \le 10^6, |S| \le 10^{18}\)).
• Dòng thứ hai ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)).

Output

• Ghi ra một dòng duy nhất là số nguyên \(K\) tìm được.

Example

8 6
3 1 5 5 2 1 3 4

2

8 100
3 1 5 5 2 1 3 4

0

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le N \le 10^3, 0 < A_i \le 10^9\).
• Subtask \(2\) (\(30\%\) số điểm): \(10^3 < N \le 10^6, 0 < A_i \le 10^9\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le N \le 10^6, -10^9 \le A_i \le 10^9\).

Bạn phát hiện một khu khoáng sản trên sao Hỏa và muốn tiến hành khai thác. Tuy nhiên do điều kiện hạn chế bạn chỉ có thể sử dụng một robot tự hành tiến hành thu thập tài nguyên ở đó. Robot mô phỏng khu vực khoáng sản trên là một lưới ô vuông kích thước \(N \cdot N\). Robot xuất phát tại ô \((1,1)\) và kết thúc tại ô \((N,N)\). Robot chỉ được di chuyển sang phải hoặc xuống dưới. Mỗi ô \((i,j)\) có phần khoáng sản trị giá \(A[i][j]\).

Robot có hai trạng thái thu hoạch: ON và OFF. Do từ trường trên sao Hỏa đặc biệt nên khi robot bước vào ô khoáng sản có giá trị lẻ, nó sẽ đảo trạng thái ON thành OFF và ngược lại.

Quy tắc khai thác như sau:

• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị lẻ: nó sẽ thu hoạch khoáng sản tại vị trí đó và thay đổi trạng thái thành OFF.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị lẻ: nó chỉ thay đổi trạng thái thành ON và không khai thác khoáng sản tại ô đó.
• Nếu trạng thái khai thác của robot đang là ON và đi vào ô khoáng sản có giá trị chẵn: nó sẽ thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái ON.
• Nếu trạng thái khai thác của robot đang là OFF và đi vào ô khoáng sản có giá trị chẵn: nó sẽ không thu hoạch khoáng sản tại vị trí đó và giữ nguyên trạng thái OFF.

Yêu cầu: Tính tổng giá trị phần quà tối đa có thể lấy được. Biết rằng ban đầu robot có trạng thái thu hoạch là ON.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(N \le 500\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên dương \(A[i][j]\) (\(A[i][j] \le 10^6\)).

Output

• Ghi ra một số nguyên duy nhất là tổng giá trị phần quà lớn nhất có thể.

Example

3
1 2 3
4 5 6
7 8 9

18

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 15\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 100\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 500\).