Maxsum

Điểm: 200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: HUBMAXS.inp

Output: HUBMAXS.out

Tác giả:

Sunlight

Dạng bài

Nam và Tài đang chơi một trò chơi toán học. Trong trò chơi này, Nam sẽ lần lượt ghi lên bảng mỗi lần một cặp số $A_i,B_i$ . Tài có nhiệm vụ sắp xếp lại các số $A$ và các số $B$ đã cho theo thứ tự nào đó sao cho: tổng lớn nhất có thể tạo được giữa các cặp $A_i,B_i$ trong cách sắp xếp đo là nhỏ nhất.

Yêu cầu: Biết cặp số $A,B$ mà Nam đã ghi lên bảng tại mỗi lượt, hãy cho biết giá trị nhỏ nhất theo mô tả ở trên mà Tài tìm được.

Input, Output và Subtasks

Input: (HUBMAXS.inp)

Dòng đầu tiên ghi số nguyên $N$ $(1\le n\le 100000)$ là số cặp $A,B$ ghi lên bảng.
$N$ dòng tiếp theo mỗi dòng ghi một cặp $A,B$ tương ứng mỗi lần ghi $(1\le A,B\le 100)$

Output: (HUBMAXS.out)

Tương ứng một cặp $A,B$ được ghi thêm lên bảng, ghi ra giá trị mà Tài tìm được.

Sample

Input (HUBMAXS.inp)

Output (HUBMAXS.out)

10
10
9

Note

Ở lượt ghi cuối, Nam ghi lên bảng $(1,4)$ . Khi đó, các giá trị tương ứng là $A(2,3,1), B(8,1,4)$ . Xét cách sắp xếp lại $A, B$ ta được $A(1,2,3),B(8,1,4)$ . Tổng lớn nhất giữa các cặp tương ứng là $9$ . Tổng này là nhỏ nhất trong các phương án sắp xếp.

Bình luận

Không có bình luận nào.