Пак Чанек — староста деревни Кхунтиен. В одну из ночей, наполненную светом, Пак Чанек неожиданно получил важное объявление, которое необходимо сообщить всем \(n\) жителям Кхунтиена.
Сначала Пак Чанек передает объявление непосредственно одному или нескольким жителям, заплатив \(p\) за каждого человека. После этого жители могут передать объявление другим жителям с помощью волшебного устройства в виде шлема. Однако за использование шлема придется заплатить. Для каждого \(i\), если \(i\)-й житель хотя бы раз получал объявление (либо непосредственно от Пак Чанека, либо от другого жителя), то он может передать его не более чем \(a_i\) другим жителям, заплатив \(b_i\) за каждую передачу.
Если Пак Чанек может также контролировать, как жители передают объявление другим жителям, то какова минимальная стоимость того, чтобы Пак Чанек оповестил всех \(n\) жителей Кхунтиена об объявлении?
Выходные данные
Для каждого набора входных данных выведите в отдельной строке минимальную стоимость уведомления всех \(n\) жителей Хунтина об объявлении.
Примечание
В первом наборе исходных данных возможной оптимальной стратегией является следующая:
- Пак Чанек передает объявление непосредственно \(3\)-му, \(5\)-му и \(6\)-му жителю. Это требует затрат в размере \(p+p+p=3+3+3=9\).
- Житель \(3\) передает сообщение жителям \(1\) и \(2\). Это требует затрат в размере \(b_3+b_3=2+2=4\).
- \(2\)-й житель передает объявление \(4\)-му. Это требует затрат \(b_2=3\).
Общая стоимость составляет \(9+4+3=16\). Можно показать, что не существует стратегии с меньшими затратами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 3
2 3 2 1 1 3
4 3 2 6 3 6
1 100000
100000
1
4 94
1 4 2 3
103 96 86 57
|
16
100000
265
|