— Но как же всех перезнакомить, если никто не хочет даже видеть друг друга? — план Дракона принцессе по-прежнему казался не особенно реализуемым.
— Не совсем так, — уточнил Дракон. — Никто не хочет незапланированных встреч. А вот, скажем, на какое-нибудь интеллектуальное состязание все охотно собираются. Есть игры, где команда состоит из двух человек...
Дракон рассказал Принцессе, что скоро в Долине Замков начнутся квалификационные соревнования по Игре в Слова. Команды, набравшие наибольшее количество очков, будут участвовать в следующем круге соревнований. При равном количестве очков более высокое место занимает команда, которая потратила меньше времени.
Опишем, как проходит квалификационная игра для одной команды.
У ведущего имеется стопка из m карточек, на каждой из которых записано по одному слову. Игроки ходят по очереди. Перед игрой они договариваются, кто из них будет делать первый ход, и сообщают об этом ведущему. Будем называть игрока, делающего первый ход, Первым игроком, а его сокомандника — Вторым игроком.
Сначала ведущий выдаёт одну карточку Первому Игроку. Первый Игрок пробует объяснить слово, записанное на карточке, Второму Игроку, не называя это слово. Когда объяснение закончено, Второй Игрок сообщает свой ответ. Если ответ Второго Игрока совпадает со словом на карточке, команде засчитывается очко. Далее ведущий выдаёт одну карточку Второму Игроку, и уже тот объясняет записанное на карточке слово Первому Игроку. Потом карточку вновь получает Первый Игрок... Игра продолжается, пока не закончатся карточки.
В этом сезоне в квалификационных играх есть важное дополнение к описанным выше правилам. При объяснении очередного слова игрок может использовать терминологию только одной предметной области. Более того, использовать терминологию некоторой предметной области в квалификационной игре можно только один раз. В правилах выделено n (n ≥ m) предметных областей.
Пара игроков X и Y, собирающаяся участвовать в квалификационной игре, очень много готовилась. Они полагают, что любой игрок пары угадает любое слово, объясняемое терминами любой предметной области. Вопрос только во времени, которое на это понадобится.
Проведя серию тренировок, они определили для каждой предметной области и каждого из игроков время, за которое игрок угадывает слово, если он выслушал объяснение с использованием терминологии этой предметной области.
Теперь они хотели бы выяснить, за какое минимально возможное время они наберут m очков. Ваша задача — вычислить это время.
В первой строке содержатся целые числа m и n (1 ≤ m ≤ n ≤ 400) — количество карточек в стопке и количество предметных областей, терминологию которых можно использовать при объяснении.
Во второй строке содержится n целых чисел p1, p2, ..., pn, где pj (1 ≤ pj ≤ 106) — время, за которое угадывает слово игрок X, если он выслушал объяснение с использованием терминологии предметной области #j.
В третьей строке содержится n целых чисел q1, q2, ..., qn, где qk (1 ≤ qk ≤ 106) — время, за которое угадывает слово игрок Y, если он выслушал объяснение с использованием терминологии предметной области #k.
В первой строке выведите целое число — минимально возможное время, которое потребуется игрокам на объяснение m слов согласно правилам игры. Игроки могут выбрать, кто из них будет делать первый ход.
3 5
5 4 7 6 2
8 3 5 4 2
9
4 4
2 4 6 8
1 4 6 7
18
В первом примере игрокам следует действовать так. Первый ход делает X; он объясняет Y слово терминами из второй предметной области, и Y угадывает слово за 3 единицы времени. Затем Y использует для объяснения термины пятой предметной области, и X угадывает слово за 2 единицы времени. И, наконец, X объясняет еще одно слово терминами из четвертой предметной области, а Y угадывает его за 4 единицы времени.
| V (XVI) открытый командный студенческий чемпионат Поволжья по спортивному программированию |
|---|
| Закончено |
