Farmer John nhận thấy mỗi con bò của mình sẽ dễ vắt sữa hơn khi có một con bò khác ở gần để động viên tinh thần. Vì vậy, ông muốn chia \(M\) con bò (\(M \leq 1\,000\,000\,000\), \(M\) chẵn) thành \(M/2\) cặp. Sau đó, mỗi cặp bò sẽ được đưa vào một chuồng riêng trong nhà kho để vắt sữa. Việc vắt sữa ở tất cả \(M/2\) chuồng sẽ diễn ra đồng thời.

Mọi chuyện hơi phức tạp hơn vì mỗi con bò của Farmer John có một sản lượng sữa khác nhau. Nếu hai con bò có sản lượng sữa \(A\) và \(B\) được ghép thành một cặp thì cần tổng cộng \(A+B\) đơn vị thời gian để vắt sữa cả hai.

Hãy giúp Farmer John xác định khoảng thời gian ngắn nhất có thể để hoàn tất toàn bộ quá trình vắt sữa, giả sử ông ghép các con bò theo cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), cho biết FJ có \(x\) con bò, mỗi con có sản lượng sữa \(y\) (\(1 \leq y \leq 1\,000\,000\,000\)). Tổng tất cả các giá trị \(x\) là \(M\), tổng số bò.

Dữ liệu ra

In thời gian ngắn nhất cần để vắt sữa đàn bò của FJ, giả sử chúng được ghép cặp tối ưu.

Ví dụ

3
1 8
2 5
1 2

10

Nguồn

USACO 2017 US Open Contest, Silver — Paired Up. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=738