Graze
Национална Олимпиада по Информатика 2012, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
Ели и овчиците й отново са в беда. След като бяха пренесени на другия бряг на реката при безкрайните сочни ливади, дойде моментът те да бъдат прибрани в кошари, за да прекарат нощта в безопасност. Размерите на кошарите са ограничени – във всяка от тях могат да се поберат по не повече от K овчици. Някои от тях може да останат полу- или изцяло празни – това не е проблем – важното е всяка овчица да е под покрив.

За простота нека си представим полето, на което пасат, като права линия. N-те овчици и M-те кошари ще бъдат представени като точки с целочислени координати Xi върху тази права. Възможно е няколко овце, няколко кошари или няколко овце и няколко кошари да имат едни и същи координати.

Животинките на Ели изминават по единица разстояние за секунда. Тоест ако например някоя от тях е с координати 42 и иска да отиде в кошара с координати 13, то за целта ще са й нужни 29 секунди. Ако пък кошарата беше на позиция 53, на овчицата щяха да са нужни 11 секунди.

Помогнете на Ели да изчисли за колко най-малко време може всички овце да бъдат прибрани.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, M и K – съответно броят овце, броят кошари и максималният брой овце, които могат да се поберат в една кошара. На следващия ред ще бъдат зададени N цели числа S1, S2, …, SN - координатите на овцете по правата. На третия ред ще бъдат зададени M цели числа B1, B2, …, BM – координатите на кошарите по правата.
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималното необходимо време, за което всички овчици могат да стигнат до кошари, без те да се препълват (тоест всяка от тях да съдържа по K или по-малко овце). Ако това е невъзможно, изведете -1.
Ограничения
  • 1 ≤ N, M, K ≤ 100,000
  • 1 ≤ Si, Bi ≤ 1,000,000
Примерен Вход Примерен Изход
7 3 3 4 9 8 2 4 6 5 2 7 2 3
Овцете с координати 4, 2, 4 и 5 се разпределят в двете кошари с координати 2, а останалите – в кошарата с координати 7. Най-много време отнема на овцата с координати 5 да стигне до кошарата с координати 2.
Мрън!