Петя готовится к своему дню рождения. Он решил, что на праздничном столе будут \(n\) разных блюд, пронумерованных от \(1\) до \(n\). Так как Петя не любит готовить, он хочет заказать эти блюда в ресторанах.
К сожалению, все блюда готовятся в разных ресторанах и поэтому Пете нужно забрать свои заказы из \(n\) разных мест. Чтобы ускорить этот процесс, он хочет заказать доставку курьером в некоторых ресторанах. Таким образом, для каждого блюда есть два варианта как Петя сможет его получить:
- блюдо привезет курьер из ресторана \(i\), в этом случае курьер прибудет через \(a_i\) минут,
- Петя самостоятельно сходит в ресторан \(i\) и заберет блюдо, на это он потратит \(b_i\) минут.
У каждого ресторана есть свои курьеры и они начинают доставку заказа в тот же момент, как Петя выходит из дома. Иными словами все курьеры работают параллельно. Петя должен посетить все рестораны в которых он не выбрал доставку, делает он это последовательно.
Например, если Петя хочет заказать \(n = 4\) блюд и \(a = [3, 7, 4, 5]\), а \(b = [2, 1, 2, 4]\), то он может заказать доставку из первого и четвертого ресторана, а во второй и третий сходить самостоятельно. Тогда курьер первого ресторана привезет заказ через \(3\) минуты, курьер четвертого ресторана привезет заказ через \(5\) минут, а Петя заберет оставшиеся блюда за \(1 + 2 = 3\) минуты. Таким образом, через \(5\) минут все блюда окажутся у Пети дома.
Найдите минимальное время, через которое все блюда могут оказаться у Пети дома.