Розвезення води

Обмеження: 2 сек., 256 МіБ

Після лиж, ковзанів та інших фізичних активностей, якими займалася парочка на День закоханих, настав час для чану.

Але на лихо, у селі, де зупинилися Зеник і Марічка через ремонтні роботи відключили воду. Пані Тарнавська в розпачі! Як же ж набрати чан для любих гостей? А інші селяни як без води?

На щастя, Зеник колись працював директором водоканалу, а Марічка — менеджеркою з логістики. Зеник придумав, що розвозити воду вони будуть автомобілями пані Тарнавської (а ви думали чиїми?). Від Зеника ідея, від пані Тарнавської автомобілі, а від Марічки — управління процесом.

У селі є одна вулиця. Вулицю представимо координатною прямою.

На цій прямій є \(n\) будинків, розташованих у точках з координатами \(h_i\) кілометрів. Потреба мешканців \(i\)-ого будинку становить \(a_i\) літрів води.

Також на вулиці є \(m\) станцій з нескінченним запасом води, розташованих у точках з координатами \(s_i\) кілометрів. На кожній станції є автомобіль із цистерною місткістю \(k\) літрів, який може набирати воду на цій станції та розвозити її до будинків. Автомобіль може набирати скільки завгодно води (не більше, ніж поміститься в цистерну) скільки завгодно разів тільки на своїй станції. До будь-якого будинку можна везти воду з будь-якої станції. Після розвезення кожен автомобіль має повернутися до своєї станції.

Марічка повинна мінімізувати сумарну відстань, яку проїдуть автомобілі, щоб покрити потреби мешканців та повернутися до своїх станцій. Вона давно не працювала в сфері логістики й забула, що робити.

Допоможіть Марічці — знайдіть мінімальну сумарну відстань, яку проїдуть автомобілі.

Вхідні дані

Перший рядок містить три цілих числа \(n\), \(m\), \(k\) — кількість будинків, кількість станцій і місткість цистерни кожного автомобіля в літрах.

Наступні \(n\) рядків містять по два цілих числа \(h_i\) та \(a_i\) — координату в кілометрах відповідного будинку та потребу води в літрах мешканців цього будинку.

Наступний рядок містить \(m\) цілих чисел \(s_i\) — координати в кілометрах станцій з водою.

Вихідні дані

В одному рядку виведіть ціле число — мінімальну сумарну відстань у кілометрах, яку повинні проїхати автомобілі, щоб розвезти воду до будинків та повернутися на свої станції.

Обмеження

\(1 \le n, m \le 10^3\),

\(1 \le k, a_i \le 10^9\),

\(0 \le h_i, s_i \le 10^6\),

\(h_i < h_{i+1}\),

\(s_i < s_{i+1}\).

10 балів:

\(1 \le n, m \le 100\),

\(1 \le k, a_i \le 100\),

\(0 \le h_i, s_i \le 10^3\);

15 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
9 2 6 4 4 7 4 11 1 13 1 20 10 27 1 29 1 30 47 47 47 10 30	334

Примітки

• Автомобіль з першої станції везе 4 л води до першого будинку й повертається на станцію. Відстань від станції до будинку становить 6 км. Автомобіль долає її у два боки, тому проїде 12 км.

• З першої станції везе 4 л до другого будинку та повертається на станцію — проїжджає 6 км.

• З першої станції 1 л до третього будинку — проїжджає 2 км.

• З першої станції 1 л до четвертого будинку, 5 л до п’ятого будинку — 20 км.

• З другої станції 1 л до шостого будинку, 5 л до п’ятого будинку — 20 км.

• З другої станції 1 л до сьомого будинку — 2 км.

• Потреби восьмого будинку можна покрити водою з другої станції, проїхавши 0 км.

• Щоб задовольнити потреби дев’ятого будинку, автомобіль з другої станції має здійснити 8 поїздок по 34 км. \(8 \cdot 34 = 272\) (км).

\(12+6+2+20+20+2+0+272=334\) (км).