22516번 - Magical Girl Sayaka-chan 다국어

문제

世の中の少女たちはキュゥべえと契約し願いを叶えてもらい,それとひきかえに魔法少女となる.使う魔法の形・効果は願いに強く影響を受ける.魔法少女さやかちゃんは最近キュゥべえと契約した新米魔法少女である.さやかの願いは「事故のため指が動かなくなり,音楽を演奏するのを諦めていた男の子を助けること」であったので,作る魔方陣は音符が輪の上に並んだ形をしている.

さやかは N 個の音符を持っており,それらを輪の上に並べることによって魔方陣を作る.音符をどのような順番で並べるかは彼女の自由である.魔方陣を作るために精神力が消費され,その量は音符の配置によって以下のように決まる.

• まず, M 個の正の整数からなる音楽的美しさ S₁, …, S_M が定められている,
• 各音符は音程を持っており,音程は 1 から M の整数 K₁, …, K_N で表される.
• 音程が a, b (a≤b) であるような 2 つの音符の間の反発力とは, [(S_a + … + S_b)⁄L] で定められる量である.ここで,L は入力で与えられる定数であり,実数 x に対して [x] は x を越えない最大の整数を表すものとする.
• さやかの消費する精神力は,各2つの隣り合う音符 (N 組存在する) の間の反発力の合計値である.

例えば音楽的美しさがそれぞれ {100, 200, 300, 400, 500} で,音程が {1, 3, 5, 4} である音符をこの順番で並べて魔方陣を作った時,消費される精神力は 37 (=[(100+200+300)⁄99]+[(300+400+500)⁄99]+[(500+400)⁄99]+[(400+300+200+100)⁄99]) となる.

使うべき音符の音程の組み合わせと各音程の音楽的美しさが与えられるので,消費される精神力の最小値を求めよ.

입력

入力は以下の形式で与えられる.

N M L
K1 K2 … KN
S1 S2 … SM

N はさやかの持っている音符の数,M は音楽的美しさの値の個数,L は反発力を定めるのに使われる定数である.

K_i は音符の音程を表し,S_j は音楽的美しさを表す.

출력

消費される精神力の最小値を 1 行に出力せよ.

제한

• 3≤N≤2,000
• 1≤M≤10⁵
• 1≤L≤10⁵
• 1≤K_i≤M
• 1≤S_j≤10⁵
• 入力値は全て整数である.

힌트