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

*“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, $t$ number of batches are manufactured. In each batch, there is $v_i$ number of Vanilla cupcakes and $c_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 $k_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.

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

The first line of each batch contains 3 integers $v_i$, $c_i$, $k_i$: number of vanilla cupcakes, number of chocolate cupcakes, number of cupcakes to be boxed respectively.

The second line of each batch contains $v_i$ number of integers $W_{v_{i,j}}$: weights of vanilla cupcakes on the vanilla conveyor belt.

The third line of each batch contains $c_i$ number of integers $W_{c_{i,j}}$: weights of chocolate cupcakes on the chocolate conveyor belt.

Constraints:

$1\leq t \leq100$

$1 \leq v_i, c_i \leq 5000$

$2 \leq k_i\leq v_i+c_i$

$\sum_{i=1}^t v_i \leq 5000$, $\sum_{i=1}^t c_i \leq 5000$

$1 \leq W_{v_{i,j}} W_{c_{i,j}} \leq 10^9$

For each batch, print 2 lines:

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

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

Input | Output |
---|---|

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 $S_1 =[ x_1, x_2, x_3, …. x_n]$ is said to be lexicographically smaller than sequence of number $S_2 = [y_1, y_2, y_3, ….. y_m]$ if their is a index $1\leq l \leq min(n,m)$ such that $x_l < y_l$and for all $1 \leq i<l$, $x_i = y_i$. Or, $S_1$ is a prefix of $S_2$ and $n<m$.

10% Solution Ratio

aropanEarliest,

BigBagFastest, 0.1s

Wojciech.324122Lightest, 283 kB

Wojciech.324122Shortest, 2002B

Login to submit

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.