PLEASE WRITE IN PYTHON

Oliver is a manager of a bank near KTH and wants to close soon. There are many people standing in the queue wanting to put cash into their accounts after they heard that the bank increased the interest rates by 42% (from 0.01% per year to 0.0142% per year).

However, there are too many people and only one counter is open which can serve one person per minute. Greedy as Oliver is, he would like to select some people in the queue, so that the total amount of cash stored by these people is as big as possible and that money then can work for the bank overnight.

There is a problem, though. Some people dont have the time to wait until the bank closes because they have to run somewhere else, so they have to be served before a certain time, after which they just leave. Oliver also turned off the infrared door sensor outside the bank, so that no more people can enter, because its already too crowded in the hall.

Task

Help Oliver calculate how much cash he can get from the people currently standing in the queue before the bank closes by serving at most one person per minute.

Input

The first line of input contains two integers N

(1N10000) and T (1T47), the number of people in the queue and the time in minutes until Oliver closes the bank. Then follow N lines, each with 2 integers ci and ti, denoting the amount of cash in Swedish crowns person i has and the time in minutes from now after which person i leaves if not served. Note that it takes one minute to serve a person and you must begin serving a person at time ti at the latest. You can assume that 1ci100000 and 0ti<T

.

Output

Output one line with the maximum amount of money you can get from the people in the queue before the bank closes.

Sample Output:

4 4 1000 1 2000 2 500 2 1200 0

Sample output:

4200 

A code in what I assume is Java:

Exatable code:

#include

#include

#include

using namespace std;

struct Client

{

int Newamount;

int wT;

Client(int m, int w)

{

Newamount = m;

wT = w;

}

};

bool checkByMoney(const Client &x, const Client &y)

{

return x.Newamount >= y.Newamount;

}

void qClient(vector &v, Client Newc)

{

int q = Newc.wT;

while(q >= 0)

{

if(v[q] == 0)

{

v[q] = Newc.Newamount;

return;

}

q--;

}

}

int main()

{

int R, S, a, min;

cin>>R>>S;

vector NewQueue(S);

vector amount;

for(int i = 0; i < R; i++)

{

cin>>a>>min;

Client Newc(a, min);

amount.push_back(Newc);

}

sort(amount.begin(), amount.end(), checkByMoney);

int total= 0;

int q = 0;

while(q < amount.size())

{

qClient(NewQueue, amount[q]);

q++;

}

for(int q = 0; q < NewQueue.size(); q++)

{

total+= NewQueue[q];

}

cout<<" ";

cout<

cout<<" ";

return 0;

}