Programming is fun, Aaron is addicted to it. In order to improve his programming skill, he decides to solve one programming problem per day. As you know, different problems have different properties, some problems are so difficult that there are few people can solve it, while some problems are so easy that almost everyone is able to tackle it.
Programming skill can be measured by an integer p. And all problems are described by two integers ai and bi. ai indicates that if and only if P >= ai, you can solve this problem. bi indicates that after you solve this problem, your programming skill can be increased by bi.
Given the initial programming skill p of Aaron, and the information of each problem, Aaron want to know the maximal programming skill he can reach after m days, can you help him?
Input
Input consists of multiple test cases (less than 40 cases)!
For each test case, the first line contains three numbers: n, m, p (1 <= n <= 100000, 1 <= m <= n, 1 <= p <= 10000), n is the number of problems available for Aaron, m, p as mentioned above.
The following n lines each contain two numbers: ai and bi (1 <= ai <= 10000, 1 <= bi <= 10000) describe the information of the i-th problem as memtioned above.
There’s a blank line between consecutive cases.
Output
For each case, output the maximal programming skill Aaron can reach after m days in a line.
Sample Input
2 2 11 2
7 3
3 1 2
1 2
2 3
3 4
Sample Output
35
/**
Input
10 8 2
1 3
1 6
2 1
2 4
3 7
4 8
5 9
6 8
7 10
12 8
Output
62
Input
10 4 2
5 9
1 6
12 8
2 1
7 10
1 3
2 4
6 8
3 7
4 8
Output
35
Input
5 3 1
1 1
1 2
2 3
3 2
6 3
Output
9
**/
// author: jfo()
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> T;
vector<T> container;
int heap[100001];
class comp
{
public:
bool operator ()(const T& t1, const T& t2)
{
if(t1.first == t2.first)
return t1.second < t2.second;
else
return t1.first < t2.first;
}
};
/
void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}
/
void HeapInsert(int h, int k, int &size)
{
++size;
h[size] = k;
int cur = size;
while(cur / 2 > 0) {
if(h[cur / 2] < h[cur])
swap(h[cur / 2], h[cur]);
cur = cur / 2;
}
}
int HeapRemoveMax(int h, int &size)
{
if(size <= 0)
return 0;
int _max = heap[1];
heap[1] = heap[size–];
int cur = 1;
while(cur 2 < size) {
if(heap[cur] >= heap[2 cur] && heap[cur] >= heap[2 cur + 1])
break;
if(heap[cur 2] < heap[2 cur + 1]) {
swap(heap[cur], heap[2 cur + 1]);
cur = 2 cur + 1;
}
else {
swap(heap[cur], heap[2 cur]);
cur = 2 cur;
}
}
if(cur 2 == size && heap[cur] < heap[2 cur]) {
swap(heap[cur], heap[2 cur]);
cur = 2 * cur;
}
return _max;
}
int main2()
{
int n, m, p;
int a, b;
int i;
while(cin >> n >> m >> p) {
container.clear();
memset(heap, 0, sizeof(heap));
for(i = 0; i < n; i++) {
cin >> a >> b;
container.push_back(make_pair<int,int>(a,b));
}
sort(container.begin(), container.end(), comp());
// for(i = 0; i < n; i++)
// cout << "(" << container[i].first << ", " << container[i].second << ")" << endl;
int index = 0;
int size = 0;
for(int j = 0; j < m; j++) {
int t = p + 1;
for(i = index; i < container.size() && container[i].first < t; i++)
HeapInsert(heap, container[i].second, size);
index = i;
int item = HeapRemoveMax(heap, size);
p += item;
}
cout << p << endl;
}
return 0;
}