Input

The input is given in the below format:

M S T L
t_{1, 1} ... t_{1, S}
t_{2, 1} ... t_{2, S}
:
t_{M, 1} ... t_{M, S}
x_1 x_2 ... x_S
n_1 ... n_M

Where the input values are all integers. The test cases used for the provisional tests and system tests satisfy the following conditions:

• (M, S) = (20, 40), (40, 80)
• T = 60
• 1 \le L
• 0 < t_{i,j} (1 \le i \le M, 1 \le j \le S)
• t_{i,1} < x_1, t_{i,j} < x_j - x_{j-1} (1 \le i \le M, 2 \le j \le S)
• T < x_1, T < x_j - x_{j-1} (1 \le i \le M, 2 \le j \le S)
• 1 \le n_i (1 \le i \le M)
• n_1 + n_2 + \dots + n_M = 1000

Output

Please output your result in the format below. If the ouput does not satisfy the planning requirements then it is considered a wrong answer.

K
p_1 p_2 ... p_K

Note that it is allowed that K < n_1 + n_2 + \dots + n_M. It is not a wrong answer if the number of units outputed is less than the amount demanded.

Scoring

Simulate the production line until the time limit "L" is reached or all the cars have been manufactured (see below). Assuming that all cars i are manufactured in m_i units when the simulation is finished, the score is determined as follows:

• If m_i = n_i for all i and the time at which all the cars are completed is t, then 10^6 \times (2 - {t \over L}) rounded to the nearest integer
• Otherwise, \displaystyle{{10^6 \over M}\sum_{i=1}^M \sqrt{m_i \over n_i}} rounded to the nearest integer

How to Simulate

The production line is simulated as seen below. In reality the position of the car and the progress of the work change constantly but for the sake of simplicity we are assuming that they change discretely in 1 second intervals.

We use the following variables:

• b: Flag indicating whether the conveyor belt is stationary or moving
• t: Current time
• y_k: Coordinates of the kth car to make.
• r(k, j): Progress of the work (k, j). The work (k, j) refers to the work at the work station j of the kth car.

Assignments to variables are denoted by \gets. Also, the work (k, j) is complete if and only if r(k, j) = t_{p_k, j}.

1. Initialize t \gets 0 and y_k \gets -(k-1)\times T, r(k, j) \gets 0.
2. Repeat the following until t = L or the work (N, S) is completed.
   1. If there is a pair of k, j satisfying "x_j = y_k and work (k, j) is not completed", then b \gets 1. If there is no such pair, set b \gets 0.
   2. For each work station j, if there is a k satisfying "the k-th car is in the work station of j and the work (k, j) is incomplete", increase r(k, j) by 1 for the smallest such k. If there is no such k, we do nothing.
   3. If b = 0, increase y_k by 1 for all k. If b = 1, then y_k is unchanged.
   4. Increase time t by 1.
3. Let m_i be the number of cars of type i completed at this time. More precisely, let m_i be the number of k satisfying r(k, S) = t_{p_k,S} and p_k = i.

Input Generation

The test cases used for provisional and system tests are generated in the following way. However, some details have been omitted, so please see testcase_generator.cpp if you want to know more.

Parameters

• \alpha = 0.5, 0.7, 0.8 (the larger the value, the longer the working time t_{i,j})
• \beta = 1.0.
• c = 1.0, 1.1 (the larger the value, the longer the work station length x_j-x_{j-1}-1)
• d = 0.1.
• f = 0, 1 (When f = 1, the input contains one prototype. The worker is not familiar with the procedure for prototypes, so the operation may take longer than for other types)
• s = 3, 4 (used to determine the values of M, S etc.)

For each of the 20 possible combinations, excluding the case where \alpha = 0.8 and c = 1.0 from the 24 possible combinations, 5 cases are generated for provisional testing and 50 cases are generated for system testing.

The list of parameters used to generate the test cases for system testing (parameters_systemtest_onlinejudge.txt; md5=4a1081f7fd143943def4e95c4979b6a6) will be made available after the contest.

Overview of the generation method

Functions that randomly generate real numbers and integers between x and y (inclusive) are represented as \mathrm{rand}(x, y) and \mathrm{randint}(x, y), respectively.

• Let M = 5 \times 2^{s-1}, S = 5 \times 2^s, T = 60, N = 1000.
• Determine t_{i,j} so that it is not extremely large with respect to T. (See below for details)
• Determine a positive real number w_i. The w_i is called the production ratio of car type i. The larger \sum_j t_{i,j} is for i, the smaller w_i tends to be. (See below for details)
• Let x_1 = l_1 + 1, x_j = x_{j-1} + l_j + 1, where l_j is the length of work station j, defined as l_j = \max(T, \max_i t_{i,j} \times c).
• L = \mathrm{round}(\mathrm{rand}(1-d, 1+d) \times (T \times N+x_S)).
• If f = 1, a car of type M is a prototype. Change the working time: t_{M,j} \gets \mathrm{randint}(t_{M,j}, x_j - x_{j-1} - 1). This change is made after the determination of x_j etc. above.
• The n_i is determined by initializing n_i = 1 and repeating the following operation N-M times.
  • Select one car type i which is not a prototype and increase n_i by 1. The probability that i is selected is proportional to w_i.

Tools

You can download the following tools here.

• visualizer.html, README-visualizer.txt
• output_checker.cpp: Program used to score the submissions.
• testcase_generator.cpp: Program used to generate input tables. Takes parameters from standard input and generates a test case.
• example-*.txt: Input and output data for practice. Please note that the data is smaller than what is actually used for judging.
• parameters_provisional.txt, parameters_systemtest.txt: This is a list of parameters for generating the equivalent test cases for provisional and system tests. The parameters are the same as for the actual test cases, except for random seeds.

testcase_generator.cpp Usage and Example

You can generate a test case yourself by compiling testcase_generator.cpp and passing in the contents of a parameter file.

For example, if you do the following in the directory where testcase_generator.cpp and parameters_provisional.txt are placed, 100 test cases will be output under provisional with the name inputXXXX.txt.

g++ -o testcase_generator testcase_generator.cpp
mkdir provisional
cd provisional
../testcase_generator < ../parameters_provisional.txt

The input part of the file name can be specified as an argument to testcase_generator.

../testcase_generator provisional < ../parameters_provisional.txt

output_checker.cpp Usage and Example

If you compile output_checker.cpp and run it with the command line arguments "input file name" and "output file name from the program of your solution" in that order, the score will be output.

g++ -o output_checker output_checker.cpp
./your_solution < provisional/input0001.txt > output0001.txt
./output_checker provisional/input0001.txt output0001.txt

Please note that the solution program uses standard input and output but the output_checker takes a filename as a command line argument.