Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

This Is Business

By Arcturus · Limits 1s, 512 MB

“Why brother why…?”
“This is Business …”

You have started a cupcake factory where two types of cupcakes are manufactured: Vanilla and Chocolate. Cupcakes are not sold separately but are sold together in boxes. Each box may contain a different number of cupcakes with the condition that at least one of each type of cupcakes should be there.

This factory has two conveyor belts, one for Vanilla cupcakes and another one for Chocolate cupcakes. Everyday, tt number of batches are manufactured. In each batch, there is viv_i number of Vanilla cupcakes and cic_i number of Chocolate cupcakes. People in your city do not like all cupcakes to be equally weighted. So different cupcakes may weigh differently in grams. Cupcakes come out sequentially on their respective conveyor belts. In each second, a controllable collector selects a conveyor belt and takes out the top cupcake to the box. The next cupcake of that conveyor belt comes to the top. All these collected cupcakes are placed sequentially in the box. From each batch, a total of kik_i number of cupcakes are packed such that the total weight of the cupcakes is maximum. The cost of packaging cupcakes depends on the sequential order of the weights of cupcakes. If there are multiple ways to select cupcakes based on weights, the lexicographically smallest order is followed considering it has the lowest cost.

Now you know the weights of each cupcake on the conveyor belts. To make a better profit you have to program the collector in such a way that the total weight of cupcakes of a box is maximized and the sequential order of weights of cupcakes in that box is lexicographically smallest. Please note that the left most cupcake is considered as the top cupcake of their respective conveyor belt.

For example:
Vanilla conveyor belt: [ 4, 3, 5, 7, 4 ] grams of vanilla cupcakes.
Chocolate conveyor belt: [ 1, 5, 3, 4 ] grams of chocolate cupcakes.
You need to choose 4 cupcakes with total weight maximized. Here, the maximum weight of 13 can be gained in the following ways:

  • 3 Vanilla 1 Chocolate: order in box: [4v, 3v, 5v, 1c], [4v, 3v, 1c, 5v], [4v, 1c, 3v, 5v] and [1c, 4v, 3v, 5v]

  • 2 Vanilla 2 Chocolate: order in box: [4v, 3v, 1c, 5c], [4v, 1c, 3v, 5c], [4v, 1c, 5c, 3v], [1c, 4v, 3v, 5c], [1c, 4v, 5c, 3v] and [1c, 5c, 4v, 3v]

  • 1 Vanilla 3 Chocolate: order in box: [4v, 1c, 5c, 3c], [1c, 4v, 5c, 3c], [1c, 5c, 4v, 3c] and [1c, 5c, 3c, 4v]

Among these ways, the sequential order of weights: [1, 4, 3, 5], is the lexicographically smallest order of weights considering it has the lowest cost.

Input

The first line of input contains one integer tt: the number of batches for today. Each of the next tt triples of lines describes one batch.

  • The first line of each batch contains 3 integers viv_i, cic_i, kik_i: number of vanilla cupcakes, number of chocolate cupcakes, number of cupcakes to be boxed respectively.

  • The second line of each batch contains viv_i number of integers Wvi,jW_{v_{i,j}}: weights of vanilla cupcakes on the vanilla conveyor belt.

  • The third line of each batch contains cic_i number of integers Wci,jW_{c_{i,j}}: weights of chocolate cupcakes on the chocolate conveyor belt.

Constraints:

  • 1t1001\leq t \leq100

  • 1vi,ci50001 \leq v_i, c_i \leq 5000

  • 2kivi+ci2 \leq k_i\leq v_i+c_i

  • i=1tvi5000\sum_{i=1}^t v_i \leq 5000, i=1tci5000\sum_{i=1}^t c_i \leq 5000

  • 1Wvi,jWci,j1091 \leq W_{v_{i,j}} W_{c_{i,j}} \leq 10^9

Output

For each batch, print 2 lines:

  • In the first line, one integer: the maximum possible weight.

  • In the second line, kik_i space-sepaeated integers: the lexicographically smallest order of weights of cupcakes in the box.

Sample

InputOutput
2
5 4 4
4 3 5 7 3
1 5 3 4
3 3 4
1 5 7
1 3 9
13
1 4 3 5
14
1 1 3 9

Lexicographical ordering means dictionary order. For example: In the dictionary 'regain' comes after 'rebuild' because 'g' comes after 'b' in the English alphabetic system. A sequence of number S1=[x1,x2,x3,.xn]S_1 =[ x_1, x_2, x_3, …. x_n] is said to be lexicographically smaller than sequence of number S2=[y1,y2,y3,..ym]S_2 = [y_1, y_2, y_3, ….. y_m] if their is a index 1lmin(n,m)1\leq l \leq min(n,m) such that xl<ylx_l < y_land for all 1i<l1 \leq i<l, xi=yix_i = y_i. Or, S1S_1 is a prefix of S2S_2 and n<mn<m.

Discussion

Statistics


10% Solution Ratio

aropanEarliest, 3w ago

BigBagFastest, 0.1s

Wojciech.324122Lightest, 283 kB

Wojciech.324122Shortest, 2002B

Submit

Login to submit

Editorial

Problem Formulation: Let’s think of each conveyor belt as a sequence of numbers Sv, Sc. We have to t...

Toph uses cookies. By continuing you agree to our Cookie Policy.