Спершу з'ясуємо, скільки цукерок кожного номера доступно.
Цукерка з номером трапляється в тих візитах, чий відрізок [l_j, r_j] містить . Щоб порахувати це для всіх одразу, скористаємось різницевим масивом: для кожного візиту робимо \mathrm{cnt}[l_j] \mathrel{+}= 1 і \mathrm{cnt}[r_j + 1] \mathrel{-}= 1, а потім беремо префіксні суми. Це дає \mathcal{O}(n + C) замість \mathcal{O}(n \cdot C).
Крім того, умова окремо обмежує: цукерок з номером можна взяти не більше ніж штук. Отже, реальна доступна кількість — це \min(i,\; \mathrm{cnt}[i]).
Тепер задача така: є предмети, де предмет номера важить грамів і доступний у певній кількості; треба взяти якнайбільше предметів сумарною вагою не більше . Оскільки нас цікавить кількість, а не цінність, працює проста жадібність: беремо цукерки за зростанням номера, тобто найлегші спочатку. Заміна будь-якої взятої цукерки на легшу невзяту ніколи не зменшує кількість, тому жадібний вибір оптимальний.
Отже, ідемо від до максимального номера і беремо
цукерок, оновлюючи використану вагу та відповідь.
Складність — \mathcal{O}(n + C), де C \le 10^5. Вага сягає 10^{12}, тому обов'язково беріть 64-бітний тип.