Supermarket

Supermarketdə satılan məhsulların $\text{Prod}$ cəmi var. Hər bir məhsul üçün x \in \textbf{Prod}, satışı müddətində d_x ədədində, supermarketə p_x gəlir gətirir (müddət satışın başladığı andan etibarən tam ədədlərlə ölçülür). Hər bir məhsulun satışı üçün dəqiq bir vaxt lazımdır.

Satış cədvəli—sıraya salınmış məhsulların alt cəmidir, Sell \subseteq Prod, belə ki, hər bir məhsul x \in Sell, müəyyən sırada, son müddəti d_x-ə qədər satılır (yəni, $x$ satışının tamamlanması d_x-dən gec olmayacaq). Satış cədvəlinin qazancı $Sell$ üçün \text{Profit}(Sell) = \sum_{x \in Sell} p_x olur. Ən yaxşı satış cədvəli—maksimum qazanc verən cədvəldir.

Məsələn, \textbf{Prod} = \{a, b, c, d\} dəstini nəzərdən keçirək: (p_a, d_a) = (50, 2), (p_b, d_b) = (10, 1), (p_c, d_c) = (20, 2) və (p_d, d_d) = (30, 1). Mümkün satış cədvəlləri cədvəldə verilib (göstərilməyib). Məsələn, Sell = \{d, a\} cədvəli məhsul $d$ satışa $0$-da başlayır və $1$-də bitir, məhsul $a$ isə $1$-də başlayıb $2$-də bitir. Hər iki məhsul son müddətinə qədər satılır. Bu, maksimal qazanc gətirən optimal cədvəldir və qazancı $80$-dir.

Verilmiş məhsullar dəstini oxuyub hər dəstə üçün optimal satış cədvəlinin qazancını hesablayan proqram yazın.