Ôn tập THT bảng B #1

Trong thời kỳ kháng chiến của dân tộc ta, đội công tác hậu cần được giao nhiệm vụ cấp bách là chế tạo đạn dược kịp thời để tiếp tế cho chiến trường. Người lính trong đội được cung cấp \(A\) đơn vị sắt và \(B\) đơn vị thuốc súng. Biết rằng, một viên đạn xuyên giáp cần một đơn vị thuốc súng và hai đơn vị sắt; một viên đạn nổ cần hai đơn vị thuốc súng và một đơn vị sắt. Với nguồn nguyên liệu có sẵn, người lính cần tính toán sao cho số lượng đạn được chế tạo là nhiều nhất. Bạn hãy lập trình xem người lính có thể chế tạo được tối đa bao nhiêu viên đạn?

Input

• Đọc từ file văn bản TIEPTE.INP hai số nguyên dương \(A\) và \(B\) (\(0 < A, B < 10^9\)).

Output

• Ghi ra file văn bản TIEPTE.OUT gồm một số nguyên dương duy nhất là số đạn tối đa có thể tạo ra.

Example

6 8

4

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(A, B \le 10^5\).
• Subtask \(2\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Trong tiết luyện tập về cách viết số tự nhiên, cô giáo cho các bạn chơi một trò chơi như sau:

Cô giáo cho \(n\) thẻ học, mỗi thẻ gồm hai số nguyên trong đó thẻ thứ \(k\) có phần bên trái là số nguyên \(A_k\), phần bên phải là số nguyên \(B_k\). Cô thực hiện bốc ra hai thẻ \(i\) và \(j\) (\(i \neq j\); \(1 \le i, j \le n\)) và gấp đôi chúng lại, thẻ \(i\) để lộ phần bên phải \(B_i\), thẻ \(j\) để lộ phần bên trái \(A_j\). Sau đó, cô đặt hai phần này cạnh nhau để tạo ra một số mới bằng cách viết số \(B_i\) rồi viết tiếp số \(A_j\) (ký hiệu là \(B_iA_j\)) và yêu cầu các bạn đọc số đó.

Ví dụ: Tấm thẻ thứ nhất chứa hai số \((12, 34)\) và tấm thẻ thứ hai chứa hai số \((567, 8)\), số ghép được từ phần bên phải thẻ 1 và phần bên trái thẻ 2 là \(34567\).

Yêu cầu: Đưa ra số lớn nhất ghép được từ việc bốc 2 trong \(n\) thẻ cho trước theo quy tắc trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(A_k, B_k\) (\(1 \le A_k, B_k \le 10^9\)).

Output

• Một số duy nhất là số lớn nhất ghép được.

Example

3
12 32
3 52
367 1

52367

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): với mọi lá bài, \(A_i < B_i\); đồng thời, với mọi \(i < n: B_i \le A_{i+1}\).
• Subtask \(3\) (\(20\%\) số điểm): không có giới hạn nào khác.

Trong một lần thám hiểm tàn tích của một thư viện cổ, Kay tìm thấy một mảnh giấy kỳ lạ có chứa một thông điệp là một xâu gồm các kí tự chữ cái thường. Tưởng chừng xâu vô nghĩa nhưng Kay phát hiện một ghi chú ở góc mảnh giấy rằng "Đây là một phần của mật mã đối xứng được sử dụng bởi một tổ chức bí ẩn".

Đáng tiếc, qua thời gian, phần mật mã đã bị mất đi một số kí tự. Nhiệm vụ của bạn là khôi phục lại mật mã đối xứng này bằng cách chèn thêm ít kí tự nhất vào xâu kí tự mà Kay tìm được.

Input

• Đọc từ file văn bản MATMA.INP một xâu \(S\).

Output

• Ghi ra file văn bản MATMA.OUT gồm một dòng duy nhất là số kí tự ít nhất cần chèn vào xâu \(S\).

Example

ab

1

acbcd

2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): độ dài của xâu \(S\) không vượt quá \(255\) kí tự.
• Subtask \(2\) (\(50\%\) số điểm): độ dài của xâu \(S\) không vượt quá \(10^3\) kí tự.

Trên bàn có \(n\) chiếc đĩa được đánh số từ \(1\) đến \(n\). Ban đầu, đĩa thứ \(i\) chứa \(i\) viên kẹo. Trong \(m\) ngày tiếp theo, mỗi ngày có một bạn học sinh đến và thay đổi lại các viên kẹo ở một số đĩa. Ngày thứ \(j\), bạn học sinh thứ \(j\) đến sẽ thực hiện việc điều chỉnh: có thể lấy bớt một vài viên kẹo hoặc thêm vào trên đĩa một vài viên mà bạn ấy mang theo. Các bạn học sinh này thống nhất với nhau rằng: sau khi thay đổi đoạn liên tiếp các đĩa từ đĩa thứ \(l_j\) đến đĩa thứ \(r_j\) đều có cùng số viên kẹo là \(c_j\). Bạn học sinh \(j\) chỉ thay đổi số kẹo trong các đĩa từ \(l_j\) tới \(r_j\), những đĩa còn lại bạn ấy không thay đổi.

Nếu tổng số kẹo hiện có trên các đĩa thứ \(l_j\) đến đĩa thứ \(r_j\) thừa hoặc thiếu so với số kẹo cần thiết để làm cho mỗi đĩa trong đoạn chứa đúng \(c_j\) viên, thì bạn học sinh sẽ lấy đi đúng số viên kẹo thừa hoặc bổ sung đúng số viên kẹo thiếu.

Sau mỗi ngày, thầy An muốn biết số lượng kẹo đã thay đổi (trị tuyệt đối của hiệu số kẹo trước và sau khi thay đổi) so với ngày hôm trước là bao nhiêu sau khi bạn học sinh hôm đó đã lấy đi hay thêm vào. Hãy lập trình giúp thầy An tính toán giá trị trên nhé!

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n, m \le 10^5\)).
• \(m\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(l_j, r_j, c_j\) (\(1 \le l_j \le r_j \le n, 1 \le c_j \le 10^6\)).

Output

• Gồm \(m\) dòng, dòng thứ \(j\) chứa số lượng kẹo đã thay đổi sau khi mà bạn \(j\) đã thêm vào hoặc lấy đi bớt so với ngày trước đó.

Example

5 3
1 3 2
2 4 3
1 5 1

0
1
11

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 1000, m \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(c_j = c_1\) với mọi \(1 \le j \le m\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.