Аркадий и Маша хотят выбрать украшения для своего общего аквариума в игре Fishdom. Всего имеется n доступных украшений, каждое из которых стоит некоторое количество монет. Для выполнения задания Аркадий и Маша должны выбрать ровно m из данных украшений, причем, конечно, они собираются потратить как можно меньше монет.
Есть одна трудность: Маше нравятся некоторые a из данных украшений, а Аркадию – некоторые b. При этом некоторые украшения могут не нравиться ни Аркадию, ни Маше, или, наоборот, нравиться обоим. Ребята хотят выбрать украшения так, чтобы каждому нравились хотя бы k из выбранных. Помогите Маше и Аркадию найти минимальную сумму монет, которую придется потратить для этого.
Выходные данные
Вывести единственное число — минимальное количество монет, которое придется потратить для выполнения всех условий. Если выполнить все требования не удастся, нужно вывести -1.
Примечание
В первом примере существует единственный вариант выбрать 3 украшения, удовлетворяющих всем требованиям — нужно взять украшения с номерами 1, 2, 3.
Во втором примере вместо украшения 3 можно взять украшение 4, которое тоже нравится Аркадию, но дешевле на одну монету.
В третьем примере невозможно выбрать 2 украшения так, чтобы они оба понравились и Маше, и Аркадию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 2
3 2 2 1
2
1 2
2
1 3
|
7
|
|
2
|
4 3 2
3 2 2 1
2
1 2
3
4 1 3
|
6
|
|
3
|
4 2 2
3 2 2 1
2
1 2
3
4 1 3
|
-1
|