Maximum Balls Transformation

Little E has n colors of balls. Initially, he has a_i balls of color i (for 1 ≤ i ≤ n). He also owns two types of tools:

1. Type 1: A tool that transforms one ball of a specified color into one ball of any color of his choice. For color i, he has b_i tools of this kind.

2. Type 2: A tool that transforms one ball of a specified color into two balls of the same color. For color i, he has c_i such tools.

After any transformation, the resulting ball can itself be used for further transformations. Each tool can be used at most once. Little E wants to know for each color i what is the maximum number of balls of color i he can end up with, and also what is the maximum total number of balls he can have at the end (when all colors are considered).

Note: A tool of Type 1 does not change the total number of balls (it merely transfers a ball from one color to another), while a tool of Type 2 increases the count in that color by 1 (since one ball becomes two). However, each tool is available only for balls of a specific color as given in the input.

Hint: For a color i, suppose we do not transfer any balls from color i itself. For any other color j (with j ≠ i), if initially a_j > 0 then one may first use all possible Type 2 tools for color j to maximize the available balls (making them up to a_j + c_j) and then use up to b_j Type 1 tools (each transferring one ball) to convert those balls to color i. Thus, the maximum number of balls that can be transferred from color j is T_j = min(a_j + c_j, b_j) (if a_j > 0, and 0 otherwise).

Then, for color i, if we denote base_i = (a_i if a_i > 0 else 0) + (sum of T_j for all j ≠ i) and provided that base_i > 0, we can also apply all available Type 2 tools for color i (each adding one ball) to obtain a final count of base_i + c_i balls of color i.

The overall maximum total number of balls is the maximum among the final counts for all colors.

inputFormat

The input consists of four lines:

• The first line contains an integer n (the number of colors).
• The second line contains n space‐separated integers a₁, a₂, ..., a_n (the initial number of balls for each color).
• The third line contains n space‐separated integers b₁, b₂, ..., b_n (the number of Type 1 tools for each color).
• The fourth line contains n space‐separated integers c₁, c₂, ..., c_n (the number of Type 2 tools for each color).

outputFormat

The output consists of two lines:

• The first line should contain n space‐separated integers. The i-th integer represents the maximum number of balls of color i that Little E can obtain.
• The second line should contain one integer, representing the maximum total number of balls (i.e. the maximum among all colors).

sample

3
1 0 2
2 1 3
0 5 1

4 9 4
9