Problem 2: Bookshelf [Neal Wu / Traditional, 2012]
 
When Farmer John isn't milking cows, stacking haybales, lining up his cows,
or building fences, he enjoys sitting down with a good book.  Over the
years, he has collected N books (1 <= N <= 100,000), and he wants to build
a new set of bookshelves to hold them all.  
 
Each book i has a width W(i) and height H(i).  The books need to be added
to a set of shelves in order; for example, the first shelf should contain
books 1...k for some k, the second shelf should start with book k+1, and so
on.  Each shelf can have a total width of at most L (1 <= L <=
1,000,000,000).  The height of a shelf is equal to the height of the
tallest book on that shelf, and the height of the entire set of bookshelves
is the sum of the heights of all the individual shelves, since they are all
stacked vertically.  
 
Please help FJ compute the minimum possible height for the entire set of
bookshelves.
 
PROBLEM NAME: bookshelf
 
INPUT FORMAT:
 
* Line 1: Two space-separated integers: N and L.
 
* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i)
        and W(i).  (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
 
SAMPLE INPUT (file bookshelf.in):
 
5 10
5 7
9 2
8 5
13 2
3 8
 
INPUT DETAILS:
 
There are 5 books.  Each shelf can have total width at most 10.
 
OUTPUT FORMAT:
 
* Line 1: The minimum possible total height for the set of
        bookshelves.
 
SAMPLE OUTPUT (file bookshelf.out):
 
21
 
OUTPUT DETAILS:
 
There are 3 shelves, the first containing just book 1 (height 5, width 7),
the second containing books 2..4 (height 13, width 9), and the third
containing book 5 (height 3, width 8).

UHJvYmxlbSAyOiBCb29rc2hlbGYgW05lYWwgV3UgLyBUcmFkaXRpb25hbCwgMjAxMl0KCldoZW4gRmFybWVyIEpvaG4gaXNuJ3QgbWlsa2luZyBjb3dzLCBzdGFja2luZyBoYXliYWxlcywgbGluaW5nIHVwIGhpcyBjb3dzLApvciBidWlsZGluZyBmZW5jZXMsIGhlIGVuam95cyBzaXR0aW5nIGRvd24gd2l0aCBhIGdvb2QgYm9vay4gIE92ZXIgdGhlCnllYXJzLCBoZSBoYXMgY29sbGVjdGVkIE4gYm9va3MgKDEgPD0gTiA8PSAxMDAsMDAwKSwgYW5kIGhlIHdhbnRzIHRvIGJ1aWxkCmEgbmV3IHNldCBvZiBib29rc2hlbHZlcyB0byBob2xkIHRoZW0gYWxsLiAgCgpFYWNoIGJvb2sgaSBoYXMgYSB3aWR0aCBXKGkpIGFuZCBoZWlnaHQgSChpKS4gIFRoZSBib29rcyBuZWVkIHRvIGJlIGFkZGVkCnRvIGEgc2V0IG9mIHNoZWx2ZXMgaW4gb3JkZXI7IGZvciBleGFtcGxlLCB0aGUgZmlyc3Qgc2hlbGYgc2hvdWxkIGNvbnRhaW4KYm9va3MgMS4uLmsgZm9yIHNvbWUgaywgdGhlIHNlY29uZCBzaGVsZiBzaG91bGQgc3RhcnQgd2l0aCBib29rIGsrMSwgYW5kIHNvCm9uLiAgRWFjaCBzaGVsZiBjYW4gaGF2ZSBhIHRvdGFsIHdpZHRoIG9mIGF0IG1vc3QgTCAoMSA8PSBMIDw9CjEsMDAwLDAwMCwwMDApLiAgVGhlIGhlaWdodCBvZiBhIHNoZWxmIGlzIGVxdWFsIHRvIHRoZSBoZWlnaHQgb2YgdGhlCnRhbGxlc3QgYm9vayBvbiB0aGF0IHNoZWxmLCBhbmQgdGhlIGhlaWdodCBvZiB0aGUgZW50aXJlIHNldCBvZiBib29rc2hlbHZlcwppcyB0aGUgc3VtIG9mIHRoZSBoZWlnaHRzIG9mIGFsbCB0aGUgaW5kaXZpZHVhbCBzaGVsdmVzLCBzaW5jZSB0aGV5IGFyZSBhbGwKc3RhY2tlZCB2ZXJ0aWNhbGx5LiAgCgpQbGVhc2UgaGVscCBGSiBjb21wdXRlIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGhlaWdodCBmb3IgdGhlIGVudGlyZSBzZXQgb2YKYm9va3NoZWx2ZXMuCgpQUk9CTEVNIE5BTUU6IGJvb2tzaGVsZgoKSU5QVVQgRk9STUFUOgoKKiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIEwuCgoqIExpbmVzIDIuLjErTjogTGluZSBpKzEgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogSChpKQogICAgICAgIGFuZCBXKGkpLiAgKDEgPD0gSChpKSA8PSAxLDAwMCwwMDA7IDEgPD0gVyhpKSA8PSBMKS4KClNBTVBMRSBJTlBVVCAoZmlsZSBib29rc2hlbGYuaW4pOgoKNSAxMAo1IDcKOSAyCjggNQoxMyAyCjMgOAoKSU5QVVQgREVUQUlMUzoKClRoZXJlIGFyZSA1IGJvb2tzLiAgRWFjaCBzaGVsZiBjYW4gaGF2ZSB0b3RhbCB3aWR0aCBhdCBtb3N0IDEwLgoKT1VUUFVUIEZPUk1BVDoKCiogTGluZSAxOiBUaGUgbWluaW11bSBwb3NzaWJsZSB0b3RhbCBoZWlnaHQgZm9yIHRoZSBzZXQgb2YKICAgICAgICBib29rc2hlbHZlcy4KClNBTVBMRSBPVVRQVVQgKGZpbGUgYm9va3NoZWxmLm91dCk6CgoyMQoKT1VUUFVUIERFVEFJTFM6CgpUaGVyZSBhcmUgMyBzaGVsdmVzLCB0aGUgZmlyc3QgY29udGFpbmluZyBqdXN0IGJvb2sgMSAoaGVpZ2h0IDUsIHdpZHRoIDcpLAp0aGUgc2Vjb25kIGNvbnRhaW5pbmcgYm9va3MgMi4uNCAoaGVpZ2h0IDEzLCB3aWR0aCA5KSwgYW5kIHRoZSB0aGlyZApjb250YWluaW5nIGJvb2sgNSAoaGVpZ2h0IDMsIHdpZHRoIDgpLg==