Bedao Grand Contest 17 - Bán vé tháng

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Thành phố H vừa mới mở tuyến đường sắt đô thị (Metro) đầu tiên. Sau ~10^9+7~ năm thi công, người dân rất mong chờ được trải nghiệm loại hình giao thông mới mẻ này.

Là trưởng ban tài chính của công ty Metro mới thành lập, bạn cần đặt giá vé tháng sao cho doanh thu thu về là cao nhất. Thành phố H có ~N~ người, người thứ ~i~ có thu nhập hàng tháng là ~a_i~ vàng và ~b_i~ ngọc (~a_i \ge b_i~).

Bạn cần đặt giá vé tháng là ~x~ vàng / ~y~ ngọc, sao cho ~x \ge y~. Khi đó mỗi người dân sẽ quyết định mua hay không mua vé tháng như sau:

  • Nếu ~a_i \ge x~, người thứ ~i~ sẽ mua vé tháng với giá ~x~ vàng.

  • Nếu ~a_i < x~ và ~b_i \ge y~, người thứ ~i~ sẽ mua vé tháng với giá ~y~ ngọc.

  • Nếu ~a_i < x~ và ~b_i < y~, người thứ ~i~ sẽ không mua vé tháng.

Hãy tìm cách đặt giá vé tháng sao cho doanh thu (bằng tổng số vàng và số ngọc) hàng tháng thu về là cao nhất.

Input

Dòng đầu tiên gồm 1 số nguyên ~N~ (~1 \le N \le 150000~): số người dân ở thành phố H.

~N~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~a_i~ và ~b_i~ (~0 \le b_i \le a_i \le 10^9~) là thu nhập hàng tháng của người thứ i.

Output

In ra 1 số nguyên là doanh thu (bằng tổng số vàng và số ngọc) hàng tháng cao nhất có thể thu về.

Scoring

Subtasks

Subtask Điểm Giới hạn
1 ~12~ ~N, A_i, B_i \leq 100~
2 ~14~ ~N \leq 300~
2 ~19~ ~N \leq 3000~
2 ~14~ ~B_i = 0~
2 ~19~ ~A_i = B_i~
2 ~11~ ~N \leq 50000~
7 ~11~ Không có điều kiện gì thêm

Sample Input 1

5
80 20
60 50
40 40
15 10
70 30

Sample Output 1

220

Sample Input 2

1
50 0

Sample Output 2

50

Comments

Please read the guidelines before commenting.