Background

When Little E was playing the Somzig game, they could not handle it because there was not enough time to operate, so this problem came up.

Problem Description

Little E has $n$ colors of balls, and for color $i$ there are $a_i$ balls. There are two types of tools. The first type can change a ball of a specified color into a ball of any color. The second type can change a ball of a specified color into two balls of this color. A ball after being transformed can also be transformed again using tools. For color $i$, there are $b_i$ tools of the first type and $c_i$ tools of the second type. Little E wants to know, if each tool can be used at most once, then for each color $i$, what is the maximum possible number of balls of color $i$ in the end. Also, what is the maximum possible total number of balls in the end.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th integer denotes $a_i$.

The third line contains $n$ integers, where the $i$-th integer denotes $b_i$.

The fourth line contains $n$ integers, where the $i$-th integer denotes $c_i$.

Output Format

The first line contains $n$ integers, where the $i$-th integer denotes the maximum possible number of balls of color $i$ in the end if each tool can be used at most once.

The second line contains one integer, denoting the maximum possible total number of balls in the end if each tool can be used at most once.

2
1 2
1 2
1 0

4 3
4

Hint

Subtasks

It is guaranteed that $1 \le n \le 351493$.

It is guaranteed that $0 \le a_i, b_i, c_i \le 10^9$.

Problem Usage Agreement

From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational Contest 2024) Preliminary.

All mentions of “this repository” below refer to the THUPC2024 Preliminary official repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or repost the problems in this repository for free.

2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special access permissions to these problems.

3. If conditions permit, please also provide ways to obtain resources such as testdata, reference solutions, and editorials when using the problems in this repository; otherwise, please attach the GitHub link of this repository.

Translated by ChatGPT 5