TopCoder

thtsshz
Things not worth doing are not worth doing well.

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

31.5% (29/92)

Tags

Description


傳說在ABCLS國中有兩個樹朋友的聚落, CKC, INF.
很巧的是, 這兩個樹朋友聚落的樹都排成一條直線.
而更巧的是, 這兩個聚落居然都是水平線!!

由於實在太神奇了, 兩邊聚落決定進一步加強友誼,
為此, 他們打算在兩邊各選出 k 棵樹, 並在之間建立道路.
不過, 為了道路施工的方便, 他們希望任兩條道路都不相交.

假設每建立 1 單位長的道路需要 c 元,
你能夠幫助他們算出, 至少需要多少元的預算嗎?

Input Format

第一行有五個自然數 n, m, k, c, d.
n 代表 CKC 聚落中有幾棵樹,
m 代表 INF 聚落中有幾棵樹,
d 表示兩個聚落的直線距離.
第二行有 n 個數字代表 CKC 聚落中的樹的 x 座標.
第三行有 m 個數字代表 INF 聚落中的樹的 x 座標.
(1 <= k <= n, m <= 400)
(1 <= c <= 100. 1 <= ni, mi, d <= 10000)
(保證任兩個 ni 不相同, 任兩 mi 也不相同)

Output Format

請輸出一個數代表至少需要多少預算.
(雖然樹朋友幣是可以有小數點的,
不過為了方便申請經費, 他們希望最後的總預算是整數.)

Sample Input 1

3 4 2 1 1
4 8 9
1 4 5 8

Sample Output 1

2

Hints

恩...為什麼圖片中INF的樹不是一條線呢?
其實是因為出題者畫完之後才發現這件事, 所以就不改了(?)

Problem Source

原TIOJ1624 / Problem Setter:worm

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5