Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

HP09ANTS - Vương quốc Kiến

Ở Vương quốc Kiến, các con kiến xây một con đường hầm dài và thẳng. Mỗi gia đình kiến định cư tại một vị trí trên con đường này, tại đây chúng sống và dự trữ thức ăn để qua mùa đông giá lạnh.

Các con kiến làm việc rất hiệu quả, chúng đã nhặt được nhiều hạt lúa mì cho gia đình của mình. Để động viên cổ vũ các gia đình kiến và đảm bảo tính công bằng, Nữ hoàng Kiến quyết định mỗi gia đình sẽ được đón tiếp K thành viên của Hoàng gia (số lượng như nhau đối với mỗi gia đình) đến ăn tiệc vào ngày Giáng sinh. Mỗi thành viên sẽ ăn đúng 1 hạt lúa mì.

Vì số lượng hạt lúa mì dự trữ của từng gia đình có thể khác nhau nên các gia đình Kiến đã cùng nhau thoả thuận, những hạt lúa mì trong mỗi gia đình ngoài việc dùng để đón tiếp các thành viên của Hoàng gia, nó còn dùng vào việc hỗ trợ chung bằng cách đem tặng cho những gia đình khác. Trong trường hợp đem tặng thì gia đình tặng phải vận chuyển những hạt lúa mì đến gia đình được tặng, mỗi 1 mét đường đi, những con kiến tham gia vận chuyển sẽ ăn 1 hạt lúa mì của gia đình tặng và không phụ thuộc vào số lượng vận chuyển.

Yêu cầu

Viết chương trình xác định số lượng tối đa K các thành viên của Hoàng Gia mà các gia đình kiến có thể đón tiếp (như nhau cho mọi gia đình).

Input

  • Dòng 1: Ghi số nguyên N là số gia đình Kiến.
  • N dòng tiếp theo: Dòng thứ i là thông tin về gia đình i, gồm 2 số Ai và Bi, Ai là vị trí sinh sống của gia đình kiến thứ i (bằng khoảng cách từ của hầm vào) và Bi là số lượng hạt lúa mì mà gia đình kiến thứ i gom nhặt được. Các gia đình được viết theo thứ tự trên đường hầm (từ ngoài vào trong).

Output

  • Ghi số K (số lượng thành viên tối đa mà các gia đình kiến có thể tiếp đón).

Giới hạn

  • 1 <= N <= 400 000
  • 0 <= Ai, Bi <= 1 000 000 000
  • Không có hai gia đình nào nằm ở cùng một vị trí

Ví dụ

Input
3 
20 100 
30 80
200 150

Output
85

Được gửi lên bởi:AnhDQ
Ngày:2009-11-07
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET

hide comments
2018-10-08 11:34:43
nhật hào sạch
2017-06-19 09:18:40
bài này sử dụng thuật toán con trâu điên là 100 thôi
2017-06-19 04:34:38 Bùi Bảo Duy


Last edit: 2017-06-19 04:34:49
2017-06-19 04:31:00
con bò cười thì mình không biết. Bài này ae cứ việc sử dụng thuật toán dấu chấm tọa độ là AC
2017-06-18 17:52:13
Thuật toán con bò cười là AC !
2017-06-18 17:13:40


Last edit: 2017-06-18 17:14:10
2015-10-25 14:33:50 xin đừng quên tôi
splay tree
2015-07-31 18:22:15 N�ng D�n John
chặt nhị phân =))
2013-05-17 10:03:48 ðẹp trai bẩm sinh
88 bạn ơi
2012-01-06 15:59:18 Noyethug
dễ TLE quá..:(

Last edit: 2012-05-14 12:20:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.