Задача №111518. Расписание маршруток
Оценив последние успехи вашего друга в экономическом отделе компании, владеющей сетью маршрутных такси, директор повысил его до главного диспетчера. Теперь друг указывает, на какой маршрут должна выходить та или иная маршрутка.
В автопарке компании есть \(n\) маршруток, \(i\)-ая маршрутка номинально вмещает \(a_i\) пассажиров. По договору с департаментом транспорта города компания обязана обслуживать \(m\) маршрутов. Накопленная статистика говорит, что оптимальнее всего, если \(j\)-ый маршрут обслуживает такси номинальной вместимостью \(b_j\) пассажиров. Каждая маршрутка приписывается не более чем к одному маршруту, каждому маршруту приписывается не более одной маршрутки.
Разумеется, каждый уважающий себя диспетчер при назначении маршруток на маршруты старается минимизировать потери, которые бывают следующими:
- если \(i\)-ая маршрутка обслуживает \(j\)-ый маршрут, то компания теряет \(|a_i-b_j|\) у.е., так как чем меньше заполнено такси, тем больше не используются его возможности, а чем больше переполнено такси, тем чаще его приходится ремонтировать;
- от каждой простаивающей маршрутки, то есть такой, которой не назначен ни один маршрут, компания несет убыток \(p\) у.е.;
- компании приходится платить штраф \(q\) у.е. департаменту транспорта за каждый не обслуживаемый маршрут.
В очередной раз вы хотите помочь другу и написать для него программу, облегчающую ему работу.
В первой строке входного файла находятся четыре целых числа — \(n\), \(m\), \(p\), \(q\) (\(1\leq n,m \leq 10^3\), \(0 \leq p,q \leq 10^4\)).
Во второй строке через пробел указаны целые числа \(a_1\), ..., \(a_n\) (\(1\leq a_i \leq 10^4\)).
В третьей строке через пробел указаны целые числа \(b_1\), ..., \(b_m\) (\(1\leq b_j \leq 10^4\)).
Выведите единственное число — минимально возможные потери компании.
В примере 1 первая маршрутка назначена на второй маршрут с потерями \(|22-20|=2\) у.е., вторая маршрутка назначена на первый маршрут с потерями \(|12-11|=1\) у.е.. Итого: потери 3 у.е..
В примере 2 одна из маршруток назначается на единственный маршрут с нулевым штрафом, а вторая вынуждена простаивать. Итого: потери 100 у.е.
2 2 100 100 22 12 11 20
3
2 1 100 500 13 13 13
100