An có một con cá với hai mặt đối xứng, diện tích mỗi mặt là ~s~. Quy trình nướng cá như sau:

1. Nướng mặt trước: mất ~k \times s~ phút.
2. Nướng mặt sau: mất ~k \times s~ phút.
3. Để nguội: ~k~ phút.

Biết tổng thời gian từ lúc bắt đầu nướng đến khi có thể ăn là ~m~ phút. Cho ~k~ và ~m~, hãy tính ~s~.

Dữ liệu

Một dòng duy nhất chứa hai số nguyên dương ~k~ và ~m~ (~1 \le k, m \le 100~).

Kết quả

In ra một số nguyên duy nhất là giá trị ~s~. Dữ liệu đảm bảo ~s~ luôn là số nguyên dương.

Ví dụ

Giải thích: với test 1, ~s = 1~, tổng thời gian là ~3 \cdot 1 + 3 \cdot 1 + 3 = 9~.

Ràng buộc

• Subtask 1 ~(50\%~ điểm): ~k = 1~.
• Subtask 2 ~(30\%~ điểm): ~k \times 3 = m~.
• Subtask 3 ~(20\%~ điểm): không có ràng buộc bổ sung.

Cho dãy ~A~ gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~. Hãy cho biết dãy ~A~ có bao nhiêu cặp phần tử mà tổng của chúng chia hết cho ~3~.

Dữ liệu

• Dòng 1: số nguyên dương ~N~ (~2 \le N \le 10^6~).
• Dòng 2: ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ (~1 \le a_i \le 10^{15}~).

Kết quả

Một số nguyên duy nhất là số cặp phần tử có tổng chia hết cho ~3~.

Ví dụ

Giải thích: có ~3~ cặp thỏa mãn là ~(7, 8)~, ~(8, 4)~, ~(8, 7)~.

Ràng buộc

• Subtask 1 ~(50\%~ điểm): ~N \le 10^3~.
• Subtask 2 ~(50\%~ điểm): không có ràng buộc bổ sung.

Cửa hàng bán ~N~ loại kẹo, mỗi loại có số lượng vô hạn. Với loại kẹo thứ ~i~ (~1 \le i \le N~):

• Viên kẹo có thứ tự lẻ (viên thứ ~1, 3, 5, \ldots~) có giá ~x_i~ đồng.
• Viên kẹo có thứ tự chẵn (viên thứ ~2, 4, 6, \ldots~) có giá ~y_i~ đồng.

An có ~M~ đồng và muốn mua tổng số viên kẹo nhiều nhất có thể, tổng chi phí không vượt quá ~M~. Hãy xác định số lượng kẹo tối đa.

Dữ liệu

• Dòng đầu tiên: hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^5~, ~1 \le M \le 10^{18}~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~x_i~ và ~y_i~ (~1 \le x_i, y_i \le 10^9~).

Kết quả

Một số nguyên duy nhất là số lượng kẹo tối đa.

Ví dụ

Ràng buộc

• Subtask 1 ~(25\%~ điểm): ~N \le 10~, ~M \le 20~.
• Subtask 2 ~(20\%~ điểm): ~N \le 10^5~, ~M \le 10^9~ và ~x_i = y_i~ với mọi ~i~.
• Subtask 3 ~(25\%~ điểm): ~N \le 10^5~, ~M \le 10^9~ và ~x_i \ge y_i~ với mọi ~i~.
• Subtask 4 ~(30\%~ điểm): không có ràng buộc bổ sung.

Ban đầu, nội dung của tệp là xâu ký tự ~S~. Sau đó thực hiện ~N~ thao tác sao chép và dán. Ở thao tác thứ ~i~:

• Sao chép xâu con từ vị trí ~A_i~ đến vị trí ~B_i~.
• Chèn đoạn xâu vừa sao chép vào vị trí ~C_i~ của xâu hiện tại.

Vị trí ~x~ được hiểu là vị trí ngay sau khi đi qua ~x~ ký tự tính từ đầu xâu. Vì vậy vị trí ~0~ là đầu xâu; với xâu ~copypaste~, vị trí ~6~ nằm giữa ký tự ~a~ và ~s~, vị trí ~9~ là cuối xâu.

Nếu sau một thao tác, độ dài xâu vượt quá ~M~, các ký tự ở cuối xâu sẽ bị xóa dần từ phải sang trái cho đến khi độ dài còn đúng bằng ~M~.

Hãy xác định ~K~ ký tự đầu tiên của xâu thu được sau khi thực hiện xong cả ~N~ thao tác.

Dữ liệu

• Dòng 1: hai số nguyên ~K, M~ (~1 \le K \le 200~, ~1 \le M \le 10^9~).
• Dòng 2: xâu ~S~ gồm các chữ cái tiếng Anh thường, thỏa mãn ~K \le |S| \le \min(M, 200000)~.
• Dòng 3: số nguyên ~N~ (~1 \le N \le 200000~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~A_i, B_i, C_i~. Gọi ~L_i~ là độ dài xâu ngay trước thao tác thứ ~i~, khi đó ~0 \le A_i < B_i \le L_i~ và ~0 \le C_i \le L_i~.

Kết quả

Trên một dòng, in ra ~K~ ký tự đầu tiên của xâu sau khi thực hiện xong ~N~ thao tác.

Ví dụ

Giải thích:

1. Sao chép đoạn từ vị trí ~3~ đến ~6~, được xâu ypa, chèn vào vị trí ~8~, thu được copypastypae.
2. Sao chép đoạn từ vị trí ~1~ đến ~5~, được xâu opyp, chèn vào vị trí ~2~, thu được coopyppypastypae.
3. Sao chép đoạn từ vị trí ~4~ đến ~12~, được xâu yppypast, chèn vào vị trí ~1~, thu được cyppypastooypyppypastypae. Vì độ dài vượt quá ~M = 18~, xóa dần từ bên phải còn cyppypastooypyppypa.
4. Sao chép đoạn từ vị trí ~17~ đến ~18~, được xâu ~a~, chèn vào vị trí ~0~, thu được acypypastooypyppypa. Cắt còn acypypastooypyppyp.

Hai ký tự đầu tiên là ac.

Ràng buộc

• Subtask 1 ~(50\%~ điểm): ~M, N \le 2000~.
• Subtask 2 ~(50\%~ điểm): không có ràng buộc bổ sung.

Cho hai số nguyên dương ~N~ và ~M~.

Ta so sánh các chữ số của hai số từ hàng đơn vị đến các hàng cao hơn. Ở mỗi vị trí đang xét:

• nếu chữ số của ~N~ nhỏ hơn chữ số của ~M~, chữ số đó bị xóa khỏi ~N~;
• nếu chữ số của ~M~ nhỏ hơn chữ số của ~N~, chữ số đó bị xóa khỏi ~M~;
• nếu hai chữ số bằng nhau, giữ nguyên cả hai chữ số.

Nếu hai số có số chữ số khác nhau, ta coi các chữ số còn thiếu ở đầu số ngắn hơn là ~0~ khi so sánh. Ví dụ, khi so sánh ~12345~ và ~234~, ta coi ~234~ là ~00234~.

Sau khi thực hiện hết các phép so sánh, mỗi số mới được tạo bởi các chữ số còn lại theo đúng thứ tự ban đầu. Nếu toàn bộ chữ số của một số bị xóa, kết quả của số đó là ~YODA~.

Yêu cầu

Hãy in ra giá trị của ~N~ và ~M~ sau khi thực hiện các thao tác trên.

Dữ liệu

Gồm ~2~ dòng:

• Dòng thứ nhất chứa số nguyên ~N~.
• Dòng thứ hai chứa số nguyên ~M~.

Kết quả

In ra ~2~ dòng:

• Dòng thứ nhất là kết quả tương ứng với ~N~.
• Dòng thứ hai là kết quả tương ứng với ~M~.

Nếu toàn bộ chữ số của một số bị xóa, in ra ~YODA~.

Ví dụ

Ví dụ 1

Input

2341
6785

Output

YODA
6785

Giải thích

Ví dụ 1

So sánh từ phải sang trái:

• ~1 < 5~, nên xóa ~1~ khỏi ~N~.
• ~4 < 8~, nên xóa ~4~ khỏi ~N~.
• ~3 < 7~, nên xóa ~3~ khỏi ~N~.
• ~2 < 6~, nên xóa ~2~ khỏi ~N~.

Vì mọi chữ số của ~N~ đều bị xóa nên kết quả là ~YODA~. Số ~M~ không bị xóa chữ số nào, nên kết quả là ~6785~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, M \le 10^9~.

Chấm điểm

• Subtask 1 (~30\%~): ~N~ và ~M~ đều có đúng ~3~ chữ số.
• Subtask 2 (~70\%~): không có thêm ràng buộc bổ sung.

Bạn có ~n~ cuốn sách, được đánh số từ ~1~ đến ~n~. Mỗi cuốn sách có mức độ hấp dẫn tương ứng là ~a_1, a_2, \dots, a_n~, trong đó dãy ~a~ không giảm:

~a_i \le a_{i+1}~ với mọi ~1 \le i < n~.

Bạn sẽ đọc các cuốn sách theo đúng thứ tự từ ~1~ đến ~n~, và không được bỏ qua cuốn nào. Với mỗi cuốn sách, bạn có đúng hai lựa chọn:

• đọc toàn bộ cuốn sách đó trong ~a~ phút;
• hoặc chỉ đọc lướt trong ~b~ phút.

Chỉ những cuốn sách được đọc toàn bộ mới được tính vào tổng mức độ hấp dẫn.

Bạn có tối đa ~t~ phút. Hãy chọn cách đọc sao cho tổng mức độ hấp dẫn của các cuốn sách được đọc toàn bộ là lớn nhất.

Yêu cầu

Tính tổng mức độ hấp dẫn lớn nhất có thể đạt được.

Dữ liệu

• Dòng đầu tiên chứa bốn số nguyên ~n, t, a, b~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Kết quả

In ra một số nguyên duy nhất là tổng mức độ hấp dẫn lớn nhất.

Ví dụ

Ví dụ 1

Input

3 5 2 1
2 2 4

Output

6

Giải thích

Ví dụ 1

Một phương án tối ưu là:

• đọc toàn bộ cuốn ~1~;
• đọc lướt cuốn ~2~;
• đọc toàn bộ cuốn ~3~.

Tổng thời gian là ~2 + 1 + 2 = 5~ phút, và tổng mức độ hấp dẫn nhận được là ~2 + 4 = 6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2 \cdot 10^5~.
• ~1 \le t \le 10^9~.
• ~1 \le b < a \le 10^9~.
• ~1 \le a_i \le 10^9~.
• ~a_i \le a_{i+1}~ với mọi ~1 \le i < n~.
• Dữ liệu bảo đảm tồn tại ít nhất một phương án hợp lệ.

Chấm điểm

• Subtask 1 (~27\%~): ~a_i = a_{i+1}~ với mọi ~1 \le i < n~.
• Subtask 2 (~37\%~): ~n \le 1000~.
• Subtask 3 (~36\%~): không có thêm ràng buộc bổ sung.

Ga tàu của thành phố ~X~ có ~n~ toa tàu. Với mỗi toa tàu ~i~, ta biết:

• ~a_i~ là thứ tự vào ga của toa tàu đó;
• ~b_i~ là thứ tự rời ga của toa tàu đó.

Hai dãy ~a~ và ~b~ đều là các hoán vị của các số từ ~1~ đến ~n~.

Trên cùng một đường ray, các toa tàu hoạt động theo nguyên tắc ngăn xếp: toa vào ga sau thì phải rời ga trước. Nói cách khác, nếu hai toa tàu ~i~ và ~j~ được xếp trên cùng một đường ray và ~a_i < a_j~, thì bắt buộc phải có ~b_i > b_j~.

Có thể sử dụng nhiều đường ray khác nhau. Mỗi toa tàu phải được xếp vào đúng một đường ray.

Yêu cầu

Hãy tính số lượng đường ray ít nhất cần dùng để các thứ tự vào ga và rời ga đã cho đều có thể xảy ra.

Dữ liệu

Gồm ~3~ dòng:

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.
• Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~.

Kết quả

In ra một số nguyên duy nhất là số lượng đường ray ít nhất cần sử dụng.

Ví dụ

Ví dụ 1

Input

5
3 1 2 5 4
4 2 3 1 5

Output

4

Giải thích

Ví dụ 1

Có thể xếp hai toa tàu ~2~ và ~4~ trên cùng một đường ray. Ba toa còn lại phải nằm trên ba đường ray riêng, nên đáp án là ~4~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 2 \times 10^5~.
• ~1 \le a_i, b_i \le n~.
• ~a_i \ne a_j~ với mọi ~i \ne j~.
• ~b_i \ne b_j~ với mọi ~i \ne j~.

Chấm điểm

• Subtask 1 (~21\%~): ~n \le 10~.
• Subtask 2 (~18\%~): số lượng đường ray ít nhất cần dùng không quá ~2~.
• Subtask 3 (~31\%~): ~n \le 1000~.
• Subtask 4 (~30\%~): không có thêm ràng buộc bổ sung.

Bạn được cho hai dãy nhị phân ~a~ và ~b~ có lần lượt ~n~ và ~m~ phần tử. Mỗi phần tử của mỗi dãy chỉ nhận giá trị ~0~ hoặc ~1~.

Hãy thay thế:

• mỗi giá trị ~0~ bằng một số nguyên dương chẵn;
• mỗi giá trị ~1~ bằng một số nguyên dương lẻ.

Việc thay thế phải thỏa mãn đồng thời các điều kiện sau:

• mọi số được dùng trên cả hai dãy đều đôi một khác nhau;
• dãy sau khi thay thế của ~a~ tăng nghiêm ngặt;
• dãy sau khi thay thế của ~b~ tăng nghiêm ngặt.

Gọi giá trị lớn nhất xuất hiện trong cả hai dãy sau khi thay thế là độ đẹp của phép thay thế.

Yêu cầu

Tìm giá trị nhỏ nhất có thể của độ đẹp.

Dữ liệu

Gồm ~2~ dòng:

• Dòng thứ nhất chứa số nguyên ~n~, theo sau là ~n~ số nguyên ~a_1, a_2, \dots, a_n~.
• Dòng thứ hai chứa số nguyên ~m~, theo sau là ~m~ số nguyên ~b_1, b_2, \dots, b_m~.

Nếu ~n = 0~ hoặc ~m = 0~ thì dòng tương ứng chỉ chứa một số nguyên.

Kết quả

In ra một số nguyên duy nhất là giá trị nhỏ nhất có thể của độ đẹp.

Nếu ~n = 0~ và ~m = 0~, in ra ~0~.

Ví dụ

Ví dụ 1

Input

4 0 1 0 1
4 1 0 0 1

Output

9

Giải thích

Ví dụ 1

Một cách thay thế tối ưu là:

• ~a = [2, 3, 4, 5]~
• ~b = [1, 6, 8, 9]~

Khi đó mọi số đều đôi một khác nhau, cả hai dãy đều tăng nghiêm ngặt, và độ đẹp bằng ~9~.

Ràng buộc và chấm điểm

Ràng buộc

• ~0 \le n, m \le 5000~.
• ~a_i, b_i \in \{0, 1\}~.

Chấm điểm

• Subtask 1 (~20\%~): ~n = 0~.
• Subtask 2 (~20\%~): ~a_i = 0~ với mọi ~1 \le i \le n~.
• Subtask 3 (~30\%~): ~n, m \le 500~.
• Subtask 4 (~30\%~): không có ràng buộc bổ sung.