Единственное отличие между простой и сложной версиями — ограничения.
Сейчас в Берляндии проходят выборы и вы хотите победить в них. А точнее, вы не просто хотите победить, а сделать так, чтобы все проголосовали за вас.
Всего есть \(n\) голосующих и два варианта сделать так, чтобы они проголосовали за вас. Первый вариант это заплатить \(i\)-му голосующему \(p_i\) монет. Второй вариант, это сделать так, чтобы \(m_i\) других людей проголосовало за вас, и тогда \(i\)-й голосующий проголосует бесплатно.
Более того, процесс такого голосования проходит в несколько шагов. Например, если есть пять голосующих \(m_1 = 1\), \(m_2 = 2\), \(m_3 = 2\), \(m_4 = 4\), \(m_5 = 5\), то вы можете купить голос пятого, и в конце концов все проголосуют за вас. Множество людей, голосующих за вас, будет меняться следующим образом: \({5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}\).
Посчитайте минимально количество монет, которое вам нужно потратить, чтобы все проголосовали за вас.
Выходные данные
На каждый набор выведите одно число — минимально количество монет, которое вам нужно потратить, чтобы все проголосовали за вас.
Примечание
В первом наборе вам нужно купить голос третьего голосующего. Тогда множество людей, голосующих за вас, будет меняться следующим образом: \({3} \rightarrow {1, 3} \rightarrow {1, 2, 3}\).
Во втором наборе вам не нужно покупать голоса. Множество людей, голосующих за вас, будет меняться следующим образом: \({1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}\).
В третьем наборе вам нужно купить голоса второго и пятого голосующих. Тогда множество людей, голосующих за вас, будет меняться следующим образом: \({2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5
|
8
0
7
|