Ключове спостереження, яке робить задачу простою: порядок операцій не має значення.
Справді, кінцеве значення елемента визначається останньою застосованою до нього операцією. Тому, вирішивши, що елемент має в кінці дорівнювати c_i, достатньо застосувати до нього операцію і більше ніколи його не чіпати — це завжди можливо, хоч би де операція стояла в послідовності. Жодних додаткових обмежень порядок не накладає.
Отже, задача переформулюється так: кожному з елементів можна призначити щонайбільше одну операцію, причому операцію дозволено використати не більше k_i разів; елементи без призначення залишаються нулями. Треба максимізувати суму призначених значень.
Оскільки всі c_i невід'ємні, вигідно заповнити якомога більше елементів якомога більшими значеннями. Це класична жадібність: відсортуємо операції за спаданням c_i і братимемо їх по черзі, віддаючи кожній \min(k_i,\ \text{скільки елементів ще вільно}) елементів, доки елементи не скінчаться.
Чому це оптимально? Якщо в якомусь розв'язку елемент отримав значення c_j, тоді як залишилась невикористана «місткість» більшої операції c_i > c_j, то заміна лише збільшує суму. Повторюючи такі заміни, приходимо до жадібного розв'язку.
Складність — \mathcal{O}(m \log m) через сортування. Сума сягає 10^5 \cdot 10^5 = 10^{10}, тому обов'язково беріть 64-бітний тип.