HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi công càng nhiều càng tốt. HT airline có tất cả N phi công (N là số chẵn), các phi công được đánh số từ 1 đến N (Phi công 1 là phi công trẻ nhất, phi công i là phi công có tuổi cao thứ i,… phi công n là phi công cao tuổi nhất). HT airline cần chính xác phi hành đoàn, mỗi phi hành đoàn gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều tuổi hơn lái phụ. Hợp đồng mà công ty kí với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương của lái chính lại thấp hơn lái phụ. Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu phi hành đoàn. Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho N phi công.

Dữ liệu: Vào từ file văn bản PILOT.INP

Dòng 1 : Số nguyên dương N, là số phi công ở HT airline (2≤N≤10000; N là số chẵn).

N dòng tiếp theo, dòng thứ i là thông tin về phi công i : gồm hai số a và c viết cách nhau 1 dấu cách trống, tương ứng là tiền lương khi lái chính và tiền lương khi lái phụ. (1≤a≤c≤100 000)

Kết quả: Ghi ra file văn bản PILOT.OUT một số nguyên duy nhất là tiền lương tối thiểu phải trả cho N phi công.

Ví dụ :

PILOT.INP

6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000         

PILOT.OUT

32000

PILOT.INP

6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000          

PILOT.OUT

33000

Tài liệu tham khảo