Stealing Carrots
Time limit1sMemory limit512 MB
Each carrot appears on a fixed cycle and gains taste by a fixed increment while present; the rabbit eats at most one carrot per day and wants the maximum total taste.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Math, Implementation
- Solved
- No attempts yet
Problem
Farmer Ori of Kkwakkkwak Country has a vegetable garden with nothing planted in it. Ori plans to plant one carrot of each of N kinds in the garden and grow them for T days.
Carrot i (1 ≤ i ≤ N) initially has a taste of wi, and for each kind of carrot, T servings of fertilizer are prepared, each increasing the taste of carrot i by pi. Because Ori wants the carrots to become far tastier than their original taste, pi is always prepared to be at least wi. Ori, who loves sleep, comes out to the garden only in the morning each day to tend the carrots. For each carrot i, if carrot i is not in its place, Ori plants carrot i; otherwise, Ori gives carrot i one serving of fertilizer.
A rabbit visiting Kkwakkkwak Country learned that Ori tends the carrots only in the morning and made a plan to visit Ori's garden and steal carrots to eat. The rabbit has a small stomach, so it can eat at most one carrot per day, and it may also eat no carrot. Once it decides to eat a carrot, it eats the whole carrot without leaving any, and it visits the garden only in the afternoon to avoid meeting Ori. The rabbit wants to maximize the sum of the tastes of the carrots it eats.
Find the maximum possible sum of the tastes of the carrots the rabbit can eat over T days.
Input
The first line gives N (1 ≤ N ≤ 200,000) and T (N ≤ T ≤ 100,000,000), separated by a space. To raise the taste of the carrots sufficiently, Ori always grows them for T days, where T is at least N.
The next N lines give the wi and pi of carrot i on line i+1, separated by a space. (1 ≤ i ≤ N, 1 ≤ wi ≤ pi ≤ 100, and wi and pi are integers.)
Output
On the first line, print the maximum sum of the tastes of the carrots the rabbit can eat over T days. The answer can exceed the range of a 32-bit integer variable (int), so you must use a 64-bit integer variable (C/C++: long long, JAVA: long).