This is an approximate problem.

Mathison has been appointed the new CFO of Enigma, a major healthcare provider with headquarters in Germany.
His first task is to create exactly K new medical centres with latest-generation equipment. After a few months of intense research, he was provided with N possible locations and for each location, the amount of money the company has to pay to build in that area is known (the price usually covers everything from permits and equipment to bribes).

There are M initial clients and for each one of them, Mathison can find out how much that person is willing to pay to get treatment in each one of the potential locations. (i.e. pay[i, j] = how much client i is willing to pay to get healthy in a medical centre established in location j - this value is highly influenced by the quality of service, number of pretty nurses and the training of the doctors). Mathison has been able to find something very important about how clients choose a medical centre: a client will always go for their cheapest option (ties are usually broken by coin tosses).

The project has become way too complicated and Mathison needs your help. Can you help him impress the shareholders by maximizing the profit of this investment?

Input
The first line of the input file will contain three space-separated integers, N, K and M, representing the number of possible locations, the number of medical centres Mathison is allowed to construct and the number of initial clients.
Each of the next M lines will contain N space-separated integers, representing the price the corresponding client is willing to pay in each of the possible locations.
The last line of the input file will contain N space-separated integers, cost₁, cost₂, ..., cost_N, where cost_i = the amount of money Mathison has to pay to create a centre in location i.

Output
The first (and only) line of the output file will contain K space-separated integers, representing the indices of the locations that should be used by Mathison. The list can be provided in any order.

Constraints and notes

N = 500
1 ≤ K ≤ N
1 ≤ M ≤ 2000
A client is willing to pay at most €1000 for a consult (or treatment).
Mathison has to pay at most €1000 in order to build one new medical centre.
All indices are 1-based.

Scoring
The score for a test is compute using the profit you make from the M visits to some of the built medical centres minus the total cost of building the centres. Your job is to maximize this value.
profit formula

Because the profit can be negative your score will be normalized.
Let A = the total cost of building all N medical centres and let B = the maximum profit (the sum of the highest value a client is willing to pay). Your score will be score formula .

Test generation
Your solution will run on 50 tests. Another 100 (25 from each category) will be added after the contest ends.
There are several types of datasets:

All values in the input file are randomly generated (20 tests)
Every client has a location where they are willing to pay at most €10.
All other values are randomly generated (10 tests)
There is a small number of clients (≤ 10) who are rich and so they pay at least €800 for a consult.
All other clients are poor and pay at most €50 (10 tests).
There are at most min(N, K + 50) very cheap (≤ €50 for all clients) locations.
All other locations are expensive (≥ €500) for all clients (10 tests).