Tổng Thưởng Hoàn Thành · canuc80k0433

Có $n$ công việc cần thực hiện lần lượt trên một máy. Công việc thứ $i$ có thời lượng $a_{i}$ và một mốc mục tiêu $d_{i}$ .

Thời điểm ban đầu là $0$ . Bạn phải thực hiện tất cả công việc, mỗi lần chỉ làm một công việc và không ngắt giữa chừng. Nếu công việc $i$ hoàn thành tại thời điểm $f_{i}$ , phần thưởng của công việc đó là $d_{i} - f_{i}$ .

Phần thưởng có thể âm. Hãy chọn thứ tự thực hiện để tổng phần thưởng lớn nhất.

Input

Dòng đầu chứa số nguyên $n$ .
$n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_{i}$ và $d_{i}$ - thời lượng và mốc mục tiêu của công việc thứ $i$ .

Output

In ra một số nguyên - tổng phần thưởng lớn nhất có thể đạt được.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i}, d_{i} \leq 1 0^{6}$ .
Phải thực hiện tất cả công việc, kể cả khi phần thưởng của một công việc âm.
Kết quả cần kiểu số nguyên $64$ -bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 9$ và $a_{i}, d_{i} \leq 100$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Thực hiện theo thời lượng $1, 2, 3, 4$ cho các thời điểm hoàn thành $1, 3, 6, 10$ . Tổng thưởng là $(7 - 1) + (9 - 3) + (10 - 6) + (20 - 10) = 26$ .

Phân tích và thuật toán: Tổng d_i không phụ thuộc thứ tự, nên tối đa hóa
Phân tích và thuật toán: [ \sum(d_i-f_i) ]
Phân tích và thuật toán: tương đương tối thiểu hóa tổng thời điểm hoàn thành \sum f_i.
Phân tích và thuật toán: Sắp xếp các công việc theo thời lượng tăng dần. Duy trì thời điểm hiện tại now; sau mỗi công việc cập nhật now += a_i và cộng d_i-now vào đáp án.
Chứng minh đúng: Xét hai công việc liên tiếp có thời lượng p>q, bắt đầu tại thời điểm T. Nếu làm p trước q, tổng thời điểm hoàn thành của cặp là (T+p)+(T+p+q). Nếu đổi thành q trước p, tổng là (T+q)+(T+q+p), nhỏ hơn đúng p-q.
Chứng minh đúng: Tổng thời lượng của cặp không đổi nên thời điểm hoàn thành của mọi công việc phía sau không đổi. Vì vậy mọi nghịch thế thời lượng có thể được đổi để cải thiện hoặc giữ mục tiêu. Sau khi loại hết nghịch thế, ta nhận thứ tự thời lượng tăng dần với tổng thời điểm hoàn thành nhỏ nhất, do đó tổng phần thưởng lớn nhất.
Độ phức tạp: O(n log n) thời gian do sắp xếp và O(n) bộ nhớ.