100 Великих Украинцев
Суть одной известной телевизионной передачи заключается в следующем. Выдвигается некоторое количество кандидатур выдающихся (на чей-либо взгляд) людей, проживавших на Украине в какой-то период времени. Затем приглашенные в студию гости и зрители обсуждают различных кандидатов. Но самое интересное наступает уже после окончания передачи. В эфире объявляются номера телефонов, по которым каждый желающий может отправить со своего номера sms-сообщение (его стоимость составляет 1 гривну) с указанием номера того кандидата, которого он хочет поддержать. При этом соответствующему кандидату добавляется 1 голос. По прошествии определенного времени подводятся итоги sms-голосования и определенное количество кандидатов, имеющих наиболее высокий рейтинг, объявляются Великими (в случае если несколько кандидатов имеют равный рейтинг, а их добавление ко множеству Великих приводит к превышению заданного количества, то все они, равно как и имеющие меньший рейтинг, не считаются Великими).
Некоторая общественно-политическая организация хотела бы, чтобы некоторые определенные ею кандидаты обязательно попали в список Великих. За день до подведения итогов этой организации удалось узнать текущий рейтинг всех кандидатов, который быть может не обеспечивал требуемый результат. Как известно, повторные sms с одного и того же номера не учитываются, поэтому один из участников данной организации вышел на улицу, обращаясь к прохожим с просьбой отправить sms за кандидата, которого он назовет. Естественно, что стоимость отправки организация возмещает, и прохожий сразу же получает свою потраченную гривну.
Кроме того есть и вторая организация, цель которой заключается в том, чтобы помешать первой организации осуществить план по проталкиванию своих кандидатов. Ее представитель также стал просить отправлять прохожих сообщения за тех кандидатов, которые нужны ему.
Зная сколько денег имеет в своем распоряжении вторая организация, необходимо определить минимальную сумму, с помощью которой первая организация может сделать своих кандидатов Великими украинцами даже при самой лучшей стратегии противодействия второй организацией.
Предполагается, что население страны достаточно большое и каждый из представителей сможет найти нужное ему количество прохожих. Кроме того, за оставшееся до подведения итогов время никто из нормальных людей по своей воле не будет тратить собственных денег на всякую ерунду.
Входные данные
В первой строке задаются 3 целых числа: N - общее количество кандидатов, M - количество Великих, K - количество продвигаемых первой организацией кандидатов. Во второй строке находится сумма S, имеющаяся в распоряжении у второй организации (1 ≤ K ≤ M ≤ N ≤ 10^5, 0 ≤ S ≤ 10^9). В третьей строке записаны числа A_i (i={1...N}) - рейтинги кандидатов (0 ≤ A_i ≤ 10^9). И в четвертой - числа B_j (j={1...K}), определяющие номера кандидатов, которые должны быть сделаны Великими.
Выходные данные
Выведите минимальную сумму, которую требуется потратить первой организации для того, чтобы добиться своей цели.