Magical Girl Sayaka-chan

시간 제한2초메모리 제한512 MB

요약

주어진 음정을 가진 N개의 음표를 원 위에 배치해 인접한 음표 사이 반발력 합의 최솟값을 구한다. 반발력은 음악적 아름다움의 구간 합을 L로 나눈 값이다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

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

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

まず， M 個の正の整数からなる音楽的美しさ S1, …, SM が定められている，
各音符は音程を持っており，音程は 1 から M の整数 K1, …, KN で表される．
音程が a, b (a≤b) であるような 2 つの音符の間の反発力とは， [(Sa + … + Sb)⁄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 は反発力を定めるのに使われる定数である．

Ki は音符の音程を表し，Sj は音楽的美しさを表す．

출력

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

제한

3≤N≤2,000
1≤M≤105
1≤L≤105
1≤Ki≤M
1≤Sj≤105
入力値は全て整数である．

예제2

예제 1
입력
```
4 5 99
1 4 5 3
100 200 300 400 500
```
예상 출력
```
37
```
예제 2
입력
```
3 1 99
1 1 1
100
```
예상 출력
```
3
```