Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
| 1 | Исаакиевский собор, Русский музей | 1500 |
| 2 | Эрмитаж, Петропавловская крепость | 1200 |
| 3 | Эрмитаж | 250 |
| 4 | Русский музей | 250 |
| 5 | Петропавловская крепость | 500 |
| 6 | Исаакиевский собор, Петропавловская крепость | 1400 |
Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?
В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Нужно покрыть маршрутами все четыре объекта с наименьшими затратами. Маршруты 3, 4 и 6 вместе включают Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор и стоят 250 + 250 + 1400 = 1900 рублей. Если взять маршрут 1, он покрывает только Русский музей и собор, а для Эрмитажа и крепости потребуется маршрут 2: всего 1500 + 1200 = 2700 рублей. Любой набор без маршрута 1 или 6 требует отдельно покрыть собор; сравнение оставшихся вариантов также не даёт суммы меньше 1900 рублей. Ответ: 346.