Supermarket

Супермаркет має набір товарів $\text{Prod}$, виставлених на продаж. За кожний товар x \in \textbf{Prod}, проданий не пізніше свого дедлайну d_x (де дедлайн вимірюється у цілих одиницях часу з моменту початку розпродажу), магазин отримує прибуток p_x. На продажу кожного товару потрібно рівно одну одиницю часу.

Графік продажу — це впорядкована підмножина товарів Sell \subseteq Prod, така, що кожний товар x \in Sell (у порядку в $Sell$) продається не пізніше строку d_x (тобто його продаж має закінчитись не пізніше, ніж у момент d_x). Прибуток за графіком продажу $Sell$ дорівнює \text{Profit}(Sell) = \sum_{x \in Sell} p_x. Оптимальний графік продажу — це графік, що дає максимальний можливий прибуток.

Наприклад, розглянемо набір \textbf{Prod} = \{a, b, c, d\} з (p_a, d_a) = (50, 2), (p_b, d_b) = (10, 1), (p_c, d_c) = (20, 2) і (p_d, d_d) = (30, 1). Можливі графіки продажу наведено у таблиці (не надається). Наприклад, графік Sell = \{d, a\} означає, що продаж товару $d$ починається у момент $0$ і закінчується у момент $1$, а продаж товару $a$ починається у момент $1$ і закінчується у момент $2$. Обидва товари продані вчасно. Це оптимальний графік, і його прибуток становить $80$.

Напишіть програму, що читає набори товарів з вхідного текстового файлу і обчислює максимальний прибуток оптимального графіку продажу для кожного набору.