問題一覧 > 通常問題

No.2196 Pair Bonus

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 103
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ
0 ProblemId : 7710 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-17 00:13:04

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。