Школы
Школы
Аким области решил открыть музыкальные и спортивные школы в некоторых городах области. Всего в области n городов. Для каждого города известно, сколько детей, желающих учиться в музыкальной школе, и сколько детей, желающих учиться в спортивной школе, живут в этом городе. Аким хочет, чтобы общее количество музыкальных школ было m, и общее количество спортивных школ было s. Поэтому было решено не открывать в одном городе более одной школы (возможно, в некоторых городах не откроют ни одной школы).
Советнику Акима было поручено разработать план постройки школ, чтобы максимизировать общее количество обучающихся детей в этих школах по всей области. Помогите ему в этой нелегкой задаче.
Входные данные
В первой строке находятся три целых числа n (1 ≤ n ≤ 300000), m, s (0 ≤ min(m, s) и m + s ≤ n) - количество городов в области, количество музыкальных школ и спортивных школ которые намерен открыть Аким соответственно.
В каждой из следующих n строк по два целых числа Ai
(1 ≤ Ai
≤ 105
) и Bi
(1 ≤ Bi
≤ 105
) - количество детей, желающих учиться в музыкальной школе и спортивной школах в i-ом городе соответственно.
Выходные данные
Выведите одно целое число количество детей, обучающихся по всей области, в оптимальном плане.
3 1 1 5 2 4 1 6 4
9
7 2 3 9 8 10 6 3 5 1 7 5 7 6 3 5 4
38