TopCoder

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

34.0% (17/50)

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

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

Sample Output

2

Hints

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

Problem Source

原TIOJ1624 / Problem Setter:worm

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 2000 65536 262144
2 2000 65536 262144
3 2000 65536 262144
4 2000 65536 262144