Tolik came up with a new programming technology. He wants to persuade friends to use her. However, things are not so simple. The i-th friend agrees to use Tolik's technology if his authority is no less than ai (authority is expressed as an integer). As soon as he begins to use it, the number bi will be added to Tolik's authority (there are people who have bi <0). Help Tolik guide the true as many of his friends as possible on the path.

Input data

The first line of the input file INPUT.TXT contains two numbers: n (1 ≤ n ≤ 1000) - the number of friends with Tolik, and the initial authority of Tolik. The next n lines contain pairs of numbers ai and bi. All numbers are integers, modulo not more than 106.

Output

In the output file OUTPUT.TXT, print the number m - the maximum number of friends Tolic can carry, and then m numbers - the numbers of friends in the order in which they need to be agitated.

Be so kind as to throw an idea of ​​how this problem generally refers to graphs (graphs are indicated in the type of problem by the authors) and / or the idea of ​​a solution.

    3 answers 3

    My personal opinion: the task is utopian - since the answer tends to n.

    Conditionality of the decision:

    based on the data we have, after each conversation with a friend, we will update the persuasion queues:

    • first of all those who have lower authority than Tolik will get, and b> 0,
    • secondarily, those with higher authority than Tolik will get, and b> 0,
    • in the third place, those who have lower authority than Tolik will get, and b <0,
    • in the fourth place will be those with higher authority than Tolik, and b <0,
    • separate list of those who have b = 0

    Conventionally: "lower" and "less" include equality with the compared value.

    We will add to the list of invitees those who agreed and exclude from the queues.

    We also agree that b is an integer; it is necessary for a complete depiction of the picture of the second stage of the solution.

    The solution of the problem:

    Stage 1:

    Due to the democratic nature of the task ( if the author complicates, it will be more interesting ), at the very beginning we give in to persuasion of all the people from the first stage, thereby raising our authority, we will be able to drag some from the second stage to the first.

    We persuade those who have b = 0, add them to the list of successfully promoted. Having reached the maximum of authority, we will compile a list of hopeless ones from the remnants of the second and fourth queues.

    Stage 2:

    We have: the third turn and lists of invited and hopeless.

    Sort by ascending module b.

    Gradually losing credibility, we invite the first in the sorted list of the third queue (based on the accepted condition, b = (- 1)). We update queues. Increase the module b. If b is equal (the value is already negative), suppose that there are two such (Z and Y), for simplicity, we get the system:

    Za ? Yb + b ? Ta Ya ? Za + b ? Ta

    The system considers the following questions: is it possible for Tolik (Ta) to invite Z first and then Y, or vice versa, choose the option in which we invite the maximum quantity, that is, two, this particular sequence is the key one. Do not forget about updating the queues, and rebuilding the system after that.

    Stage 3

    Preparing of report

    Podstchet successfully promoted, and formatting the file according to the condition of the problem.

    Something like this.

    • The decision is incorrect. For example, Tolik now has 10 authority and 2 friends who have Tolik 10 and 2, respectively, bi -6 and -2, respectively. You sort and sagit the second first, you can no longer sagit, although if you agitate the first one, the second one also agitates. - Dima1998

    The standard task on the graphs, all of them (well, not quite everything, everything, but such "olympiad" ones) are solved in approximately the same way ... I advise you to take something simpler to begin with in order to "fill your hand". For example - http://www.codeabbey.com/index/task_view/sweet-harvest

    And this one can also be solved - http://www.codeabbey.com/index/task_view/paths-in-the-grid - although in this case it is inefficient, there you can figure out how to optimize.

    If you do not bother with all sorts of optimizations, and decide "in the forehead," then this is a few lines on Python. But I still hope that you somehow figure it out. If anything, help.

    Here are a couple of useful links - https://clck.ru/9Sqsr https://clck.ru/9SCaN

    • And, by chance, is this not the typical case of traveling salesman problem? - Dex
    • I would not say that the typical ... - VadimTukaev

    So. I just solved this problem for N <1000 I was looking for where to pass N <100000 (I did not find it). The task is either for greed + dynamics or greed.

    All with b> = 0 we sort ascending a and try to take. A very trivial proof if we can take i then j, while ai> aj can be done and vice versa. We sort all with b <0 descending a + b (why? Similar to the last line but a bit more cumbersome proof, try it yourself or read the analysis) Next or dn (we need to choose j from the first ones so that b would be the maximum) dp [i] [j] = max (dp [i-1] [j], if authority after positive + dp [i-1] [j-1]> = a [i] is taken into account dp [i-1] [j -1] + b [i]) and then restoring the path we get our friends themselves Or greed: it is advantageous for us to take everyone in a row and cancel the person with the smallest b in the event that it leads to the fact that we can take the current with a large b (k- in the same authority not change). My java code is http://ideone.com/kpAqgc

     private Friend[] friends; private int authority; private Main(int authority, int a[], int b[]) { this.authority = authority; friends = new Friend[a.length]; for (int i = 0; i < friends.length; ++i) { friends[i] = new Friend(a[i], b[i], i+1); } } Comparator < Friend > sortCompare = new Comparator<Friend>() { @Override public int compare(Friend o1, Friend o2) { return o2.a+o2.b-o1.a-o1.b; } }; private Friend[] solveNegativeDp(Friend[] negative) { Arrays.sort(negative, sortCompare); Integer[][] maxBSum = new Integer[negative.length+1][negative.length+1]; maxBSum[0][0] = 0; for (int i = 1; i <= negative.length; ++i) { maxBSum[i][0] = 0; for (int j = 1; j <= negative.length; ++j) { if (maxBSum[i-1][j-1] != null && authority + maxBSum[i-1][j-1] >= negative[i-1].a) { maxBSum[i][j] = maxBSum[i-1][j-1] + negative[i-1].b; } if (maxBSum[i][j] == null || maxBSum[i-1][j] != null && maxBSum[i-1][j] >= maxBSum[i][j]) { maxBSum[i][j] = maxBSum[i-1][j]; } } } int j, i = negative.length; for (j = negative.length; maxBSum[i][j] == null; --j); Friend[] negativeAdded = new Friend[j]; for (; i >= 0 && j > 0; --i) { if (maxBSum[i][j] != maxBSum[i-1][j]) { negativeAdded[--j] = negative[i-1]; } } return negativeAdded; } private Friend[] solveNegativeGreedy(Friend[] negative) { Arrays.sort(negative, sortCompare); PriorityQueue<Friend> negativeAdded = new PriorityQueue<>(1, new Comparator<Friend>() { @Override public int compare(Friend o1, Friend o2) { return o1.b - o2.b; } }); for (Friend friend : negative) { if (authority >= friend.a) { authority += friend.b; negativeAdded.add(friend); } else if (!negativeAdded.isEmpty() && authority - negativeAdded.peek().b >= friend.a && negativeAdded.peek().b < friend.b) { authority = authority - negativeAdded.poll().b + friend.b; negativeAdded.add(friend); } } Friend[] answer = negativeAdded.toArray(new Friend[negativeAdded.size()]); Arrays.sort(answer, sortCompare); return answer; } private Friend[] convinceMaxFriends(){ Vector < Friend > convinced = new Vector<>(); Vector < Friend > positive = new Vector<>(); for (int i = 0; i < friends.length; ++i) { if (friends[i].b >= 0) { positive.add(friends[i]); } } positive.sort(new Comparator<Friend>() { @Override public int compare(Friend o1, Friend o2) { return o1.a - o2.a; } }); for (Friend friend : positive) { if (authority >= friend.a) { authority += friend.b; convinced.add(friend); } } Friend[] negative = new Friend[friends.length - positive.size()]; for (int i = 0, j = 0; i < friends.length; ++i) { if (friends[i].b < 0) { negative[j++] = friends[i]; } } convinced.addAll(Arrays.asList(solveNegativeGreedy(negative))); return convinced.toArray(new Friend[convinced.size()]); } private class Friend { private int a, b, index; private Friend(int a, int b, int index) { this.a = a; this.b = b; this.index = index; } }

    You can pass here http://acmp.ru/?main=task&id_task=572 You can try to find a slightly different analysis in the day of Kopeliovich in Kharkov School 2013