ŠIOM — Prekių konteineriai

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1996_3e2_konteineriai.in

Rezultatų failas: lmio_1996_3e2_konteineriai.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Prekių konteineriai

Prekybos bazėje yra $n$ konteinerių su maisto produktais. Konteineriai sunumeruoti nuo 1 iki $n$ .

Apie kiekvieną konteinerį žinoma tokia informacija: dienų skaičius $d$ , kurioms praėjus produktai turi būti realizuojami už savikainą (t. y. be pelno) ir pelnas, kuris bus gautas, jei produktai bus parduoti iki tos datos. (Produktai pardavinėjami už savikainą nuo ( $d+1$ )-osios dienos).

Kiekvieną dieną atvežamas į parduotuvę ir realizuojamas tik vienas konteineris

Užduotis

Kokį didžiausią pelną galima gauti realizavus visus konteinerius ir kokia eilės tvarka reikia juos realizuoti, norint gauti didžiausią pelną?

Pradiniai duomenys

Pirmoje eilutėje yra skaičius $n$ , rodantis kiek iš viso yra konteinerių. Likusiose $n$ eilučių įrašyta po du sveikuosius teigiamus skaičius: pirmasis rodo dienų skaičių, antrasis – galimą pelną.

Rezultatai

Pirmoje eilutėje turi būti įrašytas pelnas, likusiose $n$ eilučių – skaičiai nuo 1 iki $n$ , rodantys konteinerių realizavimo tvarką.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
3 1 20 2 10 2 30	50 1 3 2

Ribojimai