Это сложная версия задачи. Единственное отличие в том, что в этой версии вместо перечисления количеств лепестков у каждого цветка задано для всех типов цветов (по количеству лепестков) их количество в магазине.
Девочка готовится к своему дню рождения и хочет составить невероятной красоты букет. В магазине представлено в общей сложности \(n\) различных типов цветов, для каждого из перечисленных типов цветов указано их количество в магазине. Цветок с \(k\) лепестками стоит \(k\) монет. Девочка решила, что разница в количестве лепестков между любыми двумя цветами, которые она будет использовать для составления букета, не должна превышать единицы. В то же время девочка хочет собрать букет с максимально возможным количеством лепестков. К сожалению, у неё есть только \(m\) монет, и она не может потратить больше. С каким максимальным количеством лепестков она может собрать букет?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможное количество лепестков в букете, который может собрать девочка, соблюдая все перечисленные выше условия.
Примечание
В первом наборе входных данных некоторые разрешенные букеты — это \((1, 1, 2, 2), (2, 2, 3), (1, 1), (2, 2)\). Максимум из разрешенных букетов, не превышающий \(10\), составляет \(7\) для \((2, 2, 3)\). Во втором наборе входных данных вы можете собрать разрешенный букет из \((206, 206, 207, 207, 207)\) с суммой \(1033\), что является максимальным количеством лепестков, которое может купить девушка. В третьем наборе входных данных вы можете собрать корректный букет из \((5, 5, 5, 4)\) с суммой \(19\). Видно, что ни в одном разрешенном букете не может быть \(20\) лепестков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3 10
1 2 3
2 2 1
3 1033
206 207 1000
3 4 1
6 20
4 2 7 5 6 1
1 2 1 3 1 7
8 100000
239 30 610 122 24 40 8 2
12 13123 112 1456 124 100 123 10982
6 13
2 4 11 1 3 5
2 2 1 2 2 1
8 10330
206 210 200 201 198 199 222 1000
9 10 11 12 13 14 15 16
2 10000000000
11 12
87312315 753297050
|
7
1033
19
99990
13
10000
9999999999
|