In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
The inhabitants of Byteland have recently begun to travel more often than ever before. Enterprising ByteMan has had an idea of opening a travel agency. In the first day customers came to the agency (we label them with integers ranging from to ) and each of them would like to go to a trip. Unfortunately, every customer has his requirements.
Your task is to help ByteMan in choosing the customers who should go to the trip so that ByteMan's profit is maximized.
Each customer told ByteMan what value has the trip for him/her. Let be the value of the trip for the -th customer (). If , then this customer pays debillars for the trip, and if , then ByteMan has to pay the -th customer debillars if this customer goes to the trip.
Apart from financial requirements, customers also have social requirements. The -th customer has () such requirements; the -th requirement of the -th customer is represented by a pair of integers (), (). This requirement means that if the -th customer goes to the trip, then the -th customer also has to go to the trip or the cost of the trip for the -th customer has to be lowered by debillars (it might happen in such way that for some customers the cost of the trip will decrease from positive to negative and ByteMan will have to pay some debillars to such customers, so they will go to the trip not having some of their social requirements satisfied).
Help ByteMan in choosing the customers who should go to the trip so that ByteMan's profit is maximized (the number of customers who can be taken to the trip is not bounded).
There are eleven test cases that can be downloaded from here. Each test case is in a separate file biu.in, where is the case's number (). The solution to the task should be a program that reads a single integer from the standard input and writes the solution to the 'th to the standard output. The solution to test case biu0.in is not graded.
In the first line of any output file there should be exactly one integer () - the number of customers, who should be taken to the trip by ByteMan. If the number is positive, then the second line should contain integers, separated by single spaces and denoting the numbers of customers who should be taken to the trip. If there are many optimal solutions, the output file should contain one of them. The numbers of customers can be given in any order.
In the first line there is exactly one integer (), denoting the number of customers of the travel agency. The next lines describe the customers. In the -th line () there are integers () and (), and after them pairs of integers - all numbers in the line are separated by single spaces. You may assume that every customer has at most one social requirement concerning any other customer.
For the input data:
4 5 0 6 2 1 10 3 1 -10 0 1 2 1 10 2 10
the correct result is:
3 1 2 4
If ByteMan chooses customers , he will have a profit of debillars and it is an optimal solution.
Task author: Marek Cygan.