No.2196 Pair Bonus
タグ : / 解いたユーザー数 131
作問者 : Shirotsume / テスター : とりゐ
問題文
$2N$ 人の人がいます。 人には、 $1, 2, \dots, 2N$ と番号が付けられています。Shirotsume は、この人たちに赤色または青色の帽子をかぶせようと考えています。$1$ 人がかぶる帽子は赤色か青色のうちどちらかちょうど $1$ つだけです。
かぶせた帽子の色によって、得点がもらえます。
各 $i$ $(1 \leq i \leq 2N)$ に対し、 人 $i$ に赤色の帽子をかぶせた時の得点は $A_i$ 点 、青色の帽子をかぶせた時の得点は $B_i$ 点です。
また、各 $i$ $(1 \leq i \leq N)$ について、 人 $2i - 1$ と 人 $2i$ の帽子の色が同じならば $X_i$ 点、異なるならば $Y_i$ 点のボーナス得点が得られます。
$2N$ 人それぞれに対してかぶせる帽子の色を適切に決めたとき、得点の最大値はいくらになりますか?
制約
- 入力は全て整数
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$ ($1 \leq i \leq 2N$)
- $1 \leq B_i \leq 10^9$ ($1 \leq i \leq 2N$)
- $1 \leq X_i \leq 10^9$ ($1 \leq i \leq N$)
- $1 \leq Y_i \leq 10^9$ ($1 \leq i \leq N$)
入力
入力は以下の形式で標準入力から与えられる。$N$ $A_1$ $A_2$ $\dots$ $A_{2N}$ $B_1$ $B_2$ $\dots$ $B_{2N}$ $X_1$ $X_2$ $\dots$ $X_N$ $Y_1$ $Y_2$ $\dots$ $Y_N$
出力
答えを出力せよ。
最後に改行すること。サンプル
サンプル1
入力
2 3 1 4 1 5 9 2 6 1 5 4 1
出力
29
赤色の帽子をR
、青色の帽子をB
とすると、RBBB
というかぶせ方で $29$ 点を獲得できます。
各人について、帽子の色による点数が $3 + 9 + 2 + 6 = 20$ 点です。それに加えて、人 $1$ と人 $2$ の帽子の色が異なるので $Y_1 = 4$ 点、人 $3$ と人 $4$ の帽子の色が同じなので $X_2 = 5$ 点のボーナス点が得られ、合計 $29$ 点となります。
これより多くの得点を得ることはできないので、 $29$ を出力してください。
サンプル2
入力
4 31415 92653 58979 32384 62643 38327 95028 84197 27182 81828 45904 52353 60287 47135 26624 97757 11111 33333 55555 77777 88888 66666 44444 22222
出力
806700
サンプル3
入力
5 132369990 154684955 399557792 6898866 892085082 475405438 178727727 496378193 391115300 392312020 929620757 339762612 478146585 237867511 112947139 932164889 474129303 798212953 843175854 899264953 148258026 932749041 478171985 880111286 733483895 647484075 34641657 473409219 391218034 474131840
出力
10306590358
答えは32bit整数に収まらないことがあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。