Сертифицируй это (задача E I тура окружного этапа Всероссийской олимпиады школьников 2014 - 2015)

Мэр Редисочкин сидел в своем кабинете и внимательно читал статью из газеты, которую они с Перуном-Нечитайло срывали утром. Его внимание привлекла фраза про то, что, согласно новым требованиям, организация, осуществляющая ремонтные работы, должна иметь специальный сертификат. Конечно, в статье было написано, что у фирмы «Коммуникации для города» такой сертификат есть, а у местных ремонтных организаций его нет.

Местные ремонтники подтвердили, что требования появились недавно, а сертификат получать сложно и дорого. Хотя можно скооперироваться с ремонтными организациями соседних городов.

Мэр поручил своему помощнику Потапу заняться этим вопросом, и вскоре Потап сообщил ему, что связался с ремонтниками соседних городов и выяснил следующее:

• Все n ремонтных организаций в настоящий момент согласны участвовать в приобретении сертификата при условии, что каждая организация внесет одинаковую сумму.
• Для каждой организации существует некоторая предельная сумма s_j, более которой она не заплатит ни при каких условиях.
• Каждая организация хочет заключить соглашение о намерениях, а это значит, что Потапу придется съездить в каждый из n городов. При этом он может посетить только один город в течение одного дня.

Как только Потап соберёт необходимую для получения сертификата сумму, местные ремонтники смогут конкурировать с «Коммуникациями для города». Отметим, что финансовые обязательства для всех участников соглашения наступают тогда и только тогда, когда необходимая сумма набрана. Оплата вносится всеми участниками одновременно.

Дело осложняется тем, что каждый день представитель фирмы «Коммуникации для города» Брюквин тоже посещает очередной город и убеждает местные власти обратиться к его фирме, отказавшись от услуг местных ремонтников. Брюквин умеет убеждать, и местные власти всех городов соглашаются на условия фирмы «Коммуникации для города». После этого для местных ремонтников участвовать в приобретении сертификата не имеет смысла. Даже если они ранее заключили соглашение о намерениях, они отзовут свою подпись и не будут более связаны какими-либо обязательствами. Разумеется, после этого они не будут учитываться в списке участников соглашения.

Ваша задача — определить, какова максимально возможная цена сертификата, приобретение которого Потап сможет организовать.

Считайте, что Потап всегда приезжает в город рано утром, а Брюквин — днём.

3
10 8 1
3 2 1

16

3
10 8 1
2 3 1

10