24107번 - 本棚 (Bookshelf) 다국어

20XX 年，IOI が JOI 君の住む国で開催されることになった．このニュースを聞いた JOI 君は友人に知ら せるために部屋を飛び出そうとした．しかし，あまりにも急いでいたため部屋の本棚にぶつかってしまい， 本は本棚から全て落ちてしまった．とにかく急いでいた JOI 君は，落ちた本を順番を全く考慮せず全て本棚 に入れて家を出た．帰宅後，JOI 君は滅茶苦茶な順番に並んだ本を本来の順番に戻す作業が必要になった．

JOI 君の部屋の本棚は幅 N センチメートルであり，本棚には幅 1 センチメートルの本が N 冊入っている． 本には 1 から N までの番号がふられており，本来は本棚には左から 1, . . . , N の順番で本が並べられていた． また，本 i の重さは A_i グラムである．

JOI 君は疲れていて本を同時にたくさん持ちたくなかったので，次のような操作を行うことで本棚を整 理することにした:

• 本棚に入っている本を 1 つ選び，取り出す．
• 次に，本を取り出してできた隙間に隣接している本を動かすことを何度か行う．
• 次に，取り出した本を本棚の隙間に戻す．

本を本棚から同時に 2 冊以上取り出すことはできない．

例えば，本が左から 5, 3, 4, 1, 2 の順で並んでいるとき，本 1 を取り出し，本 4 と本 3 を順に右に動かし， 本 1 を本棚に戻すことで，本棚の本を左から 5, 1, 3, 4, 2 の順にすることができる．（下図）

この操作で，JOI 君が重さ w グラムの本を本棚から取り出すとき，JOI 君はちょうど w カロリーを消費 する．また，JOI 君が重さ w グラムの本を本棚に戻すときも，JOI 君はちょうど w カロリーを消費する．ま た，本棚はなめらかな素材でできているので，JOI 君が本棚の中で本を動かすときには JOI 君はカロリー を消費しないとしてよい．

JOI 君は疲れていたので，なるべくカロリーを消費しないようにして本棚の本を本来の順番に戻すこと にした．

本の数と，それぞれの本の重さ，現在の本棚の本の並び順が与えられたとき，JOI 君が本棚の本を本来 の順番に並び替えるために消費するカロリーの合計の最小値を求めるプログラムを作成せよ．

標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれている．
• 続く N 行には本の重さの情報が書かれている．i + 1 行目 (1 ≤ i ≤ N) には，本 i の重さを表す整数 A_i が書かれている．
• 続く N 行には現在の本棚の本の並び順の情報が書かれている．j + N + 1 行目 (1 ≤ j ≤ N) には，現 在左から j 番目にある本の番号を表す整数が書かれている．

標準出力に，JOI 君が消費するカロリーの合計の最小値を表す整数を 1 行で出力せよ．

• 1 ≤ N ≤ 100 000 本の数
• 1 ≤ A_i ≤ 1 000 000 000 本 i の重さ (グラム)

この入力例では，最初本は左から 3, 4, 2, 1 の順に並んでおり，本 1, 2, 3, 4 の重さはそれぞれ 1, 6, 4, 3 グラ ムである．

JOI 君は，まず以下の操作を順番に行う：

• 本 1 を取り出す．
• 本 2，本 4，本 3 を順に右に動かす．
• 本 1 を隙間に戻す．

本棚の本は左から 1, 3, 4, 2 の順になる．本 1 の重さは 1 グラムなので JOI 君は 1 × 2 = 2 カロリーを消費 する．

次に，以下の操作を順番に行う：

• 本 2 を取り出す．
• 本 4，本 3 を順に右に動かす．
• 本 2 を隙間に戻す．

本棚の本は左から 1, 2, 3, 4 の順になる．本 2 の重さは 6 グラムなので JOI 君は 6 × 2 = 12 カロリーを消費 する．

よって JOI 君は合計 14 カロリーの消費で本を左から 1, 2, 3, 4 の順にできる．また，JOI 君が消費するカ ロリーをこれより少なくすることは不可能である．