MSCHED - Milk Scheduling

(For Vietnamese version, see below.)

 

Farmer John has N cows that need to be milked (1 <= N <= 10,000), each of which takes only one unit of time to milk.

Being impatient animals, some cows will refuse to be milked if Farmer John waits too long to milk them. More specifically, cow i produces g_i gallons of milk (1 <= g_i <= 1000), but only if she is milked before a deadline at time d_i (1 <= d_i <= 10,000). Time starts at t=0, so at most x total cows can be milked prior to a deadline at time t=x.

Please help Farmer John determine the maximum amount of milk that he can obtain if he milks the cows optimally.

Input

  • Line 1: The value of N.
  • Lines 2..1+N: Line i+1 contains the integers g_i and d_i.

Output

A single numbers denotes the maximum number of gallons of milk Farmer John can obtain.

Sample

Input:
4
10 3
7 5
8 1
2 1

Output :
25

Explanation

There are 4 cows. The first produces 10 gallons of milk if milked by time 3, and so on.

Farmer John milks cow 3 first, giving up on cow 4 since she cannot be milked by her deadline due to the conflict with cow 3. Farmer John then milks cows 1 and 2.

 

 

 

 

***

 

Nông dân John có N con bò, để vắt sữa một con bò cần 1 đơn vị thời gian.

Vốn là loài vật lười, những con bò sẽ không chịu để vắt sữa nếu John bắt chúng chờ quá lâu. Cụ thể, con bò i cho g_i gallon sữa, nhưng chỉ khi nó được vắt sữa trước thời gian d_i. Thời gian bắt đầu ở T = 0, nên có tối đa X con bò có thể được vắt sữa trước thời hạn T = X.

Hãy giúp nông dân John tính lượng sữa tối đa mà ông có thể vắt được nếu như ông chọn được cách vắt hiệu quả nhất.

Input :

 - Dòng 1 : chứa số nguyên dương N.

 - Dòng 2 -> n + 1 : dòng thứ i + 1 chứa 2 số nguyên g_i và d_i.

Output :

 - Lượng sữa nhiều nhất mà John có thể vắt.

Giới hạn :

 - 1 ≤ n ≤ 10000

 - 1 ≤ g_i ≤ 1000

 - 1 ≤ d_i ≤ 10000

Ví dụ :

Input :

 4

 10 3

 7 5

 8 1

 2 1

Output :

 25

Giải thích : John vắt sữa con bò 3, sau đó đến con 1 rồi con 2.



Added by:Kata
Date:2014-03-12
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:USACO Dec 13, Silver Div

hide comments
2022-11-01 14:34:23
Finally, university syllabus helped somewhere... XD
2020-08-13 17:08:01
If u are not getting how to do this, study about job selection problem first
2020-02-21 20:15:54
got AC using Greedy technique with segment tree
2020-02-05 20:32:29
AC in 1 go :-)
2019-07-23 08:26:12
useful testcase:
7
2 1
3 2
1 3
1 4
9 5
9 5
10 6

answer:
34

Try to assign time slot starting from deadline and in decreasing time.
2019-05-16 12:55:12
My solution keeps giving WA on the 9th test caste
2017-09-25 07:36:49
Solved using greedy strategy + fenwick tree
2017-09-02 06:37:58
Many WA's

Pretty hard not to forget about all the details of the algorithm while implementing

Heavy use of STL, N*logN, but C++14 passed in 20ms, leaving huge freedom before time limit
2017-08-23 05:17:17
WA with an algo too simple to debug.. Can't stand the unavailability of testcases :(
2017-04-22 22:34:35
Implementation of Job Sequencing Problem.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.