Введемо для кожної книжки величину c_i = b_i - a_i — саме стільки задоволення дає прочитана книжка і стільки ж віднімається, якщо книжку не прочитати.
Нехай — множина прочитаних книжок, |R| = k. Тоді загальне задоволення дорівнює
Позначимо C = \sum_{i=1}^{n} c_i — сума по всіх книжках. Тоді другий доданок дорівнює C - \sum_{i \in R} c_i, і вираз перетворюється на
Величина фіксована, тому максимізувати треба лише \sum_{i \in R} c_i — суму c_i по рівно обраних книжках. Очевидно, для цього треба взяти найбільших значень c_i.
Отже, розв'язок: порахувати всі c_i, відсортувати їх за спаданням, узяти суму перших , і вивести подвоєну цю суму мінус .
Зверніть увагу, що серед c_i бувають від'ємні, але це нічого не змінює: умова вимагає прочитати рівно книжок, тому навіть якщо всі c_i від'ємні, ми беремо найбільших (найменших за модулем).
Складність — \mathcal{O}(n \log n). Значення сягають 2 \cdot 10^9 за модулем, а сума — порядку 10^{14}, тому обов'язково беріть 64-бітний тип.