Ограничение времени 1 секунда Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
В Берляндской республике проходят выборы правителя. К сожалению, Берляндия лишь недавно отказалась от монархии, поэтому выборы в ней проходят не совсем честно.
Берляндия разбита на m районов, пронумерованных целыми числами от 1 до m. Также в Берляндии есть n избирательных участков, пронумерованных целыми числами от 1 до n, причем i-й участок находится в районе с номером ci. Исходя из опыта предыдущих лет, Фонд борьбы со вборсами определил, что на i-м участке собираются вбросить ai бюллетеней. Фонд может расставить не более, чем C наблюдателей на какие-то из участков, причем на каждый участок можно отправить не более одного наблюдателя. При этом если на i-м участке будет стоять наблюдатель, то на нем не будут вбрасывать бюллетени, а иначе, как и планировалось, будет вброшено ai бюллетеней. Также, если на участках в i-м районе суммарно будет стоять хотя бы bi наблюдателей, то на каждом участке в этом районе не вбросят ни одного бюллетеня, независимо от наличия наблюдателя на этом участке.
Фонду борьбы со вбросами определить минимально возможное количество вброшенных бюллетеней при оптимальной расстановке наблюдателей.
Формат ввода
Первая строка содержит три целых числа n, m и C — количество участков, количество районов и максимальное количество расставленных наблюдателей соответственно (1 ≤ m ≤ n ≤ 4000; 1 ≤ C ≤ 4000).
Вторая строка содержит n целых чисел c1, c2, … , cn — номера районов, в которых находятся участки (1 ≤ ci ≤ m). Гарантируется, что в каждом районе есть хотя бы один участок.
Третья строка содержит n целых чисел a1, a2, … , an — количества бюллетеней, которые планируется вбросить на участках (1 ≤ ai ≤ 2 ⋅ 105).
Последняя строка содержит m целых чисел b1, b2, ..., bm — количества наблюдателей, которые необходимо расставить в каждом из районов, чтобы на участках этого района не было вбросов (1 ≤ bi ≤ n). Гарантируется, что bi не превосходит количество участков, находящихся в i-м районе.
Формат вывода
Выведите единственное целое число — ответ на задачу.
написать на питоне
