Петя начал готовиться к ЕГЭ по информатике за два дня до экзамена. Он составил план подготовки ко всем 27 заданиям. Для каждого задания указано время подготовки (в часах) и пререквизиты — задания, которые необходимо освоить раньше. Петя начинает изучать задание сразу, как только все его пререквизиты освоены. Независимые задания Петя учит параллельно (левым полушарием — логику, правым — Python, третьим — ничего, оно спит).
| № | Задание | Время | Нужно сначала |
|---|
| 1 | Графы и таблицы | 6 | — |
| 2 | Таблицы истинности | 8 | — |
| 3 | Базы данных | 10 | 9 |
| 4 | Кодирование Фано | 5 | — |
| 5 | Алгоритмы с числами | 7 | — |
| 6 | Черепаха/Чертёжник | 8 | 5 |
| 7 | Кодирование звука | 6 | 4 |
| 8 | Комбинаторика | 10 | 5 |
| 9 | Электронные таблицы | 4 | — |
| 10 | Поиск в тексте | 3 | 9 |
| 11 | Объём памяти | 5 | 4 |
| 12 | Машина Тьюринга | 15 | 5; 2 |
| 13 | IP-адресация | 6 | — |
| 14 | Системы счисления | 8 | 5 |
| 15 | Логика и тождества | 12 | 2 |
| 16 | Рекурсия | 14 | 5 |
| 17 | Обработка посл-тей | 10 | 9; 5 |
| 18 | Робот-сборщик | 12 | 1; 5 |
| 19 | Теория игр (1 ход) | 8 | — |
| 20 | Теория игр (2 хода) | 10 | 19 |
| 21 | Теория игр (стратегия) | 12 | 20 |
| 22 | Параллельные процессы | 8 | 1 |
| 23 | Исполнитель (ДП) | 14 | 5; 8 |
| 24 | Обработка строк | 10 | 5; 10 |
| 25 | Делители и простые | 16 | 5 |
| 26 | Жадные/DP на массивах | 20 | 5; 8; 16 |
| 27 | Финальный босс | 24 | 5; 8; 16; 17 |
Петя не обязан готовиться ко всем 27 заданиям — он может пропустить самые сложные. Однако если задание требует пререквизит, Петя обязан его изучить (и он тоже войдёт в число решённых).
Определите минимальное время (в часах), за которое Петя подготовится к решению хотя бы 17 заданий (это примерно 70 тестовых баллов — достаточно для приличного вуза).
Мама Пети подсчитала: если готовиться ко всем 27 последовательно, нужен 271 час. У Пети двое суток. Мама рекомендует расставлять приоритеты.