Lindsay is koopverslaafd. Telkens er een promotie is, waarbij je bij het kopen van drie artikelen er slechts twee moet betalen, koopt ze alles op.

Indien Lindsay naar de kassa gaat met zeven artikelen, met als kostprijzen €400, €350, €300, €250, €200, €150 en €100 dan krijgt ze een korting van €250. Twee artikelen werden immers niet aangerekend, en de kassa rekent natuurlijk de twee goedkoopse artikelen niet aan.

Al snel beseft ze dat ze meer korting kan krijgen, namelijk door in verschillende beurten naar de kassa te gaan. Als ze de eerste keer aan de kassa passeert met de kostprijzen €400, €350 en €300 dan krijgt ze meteen al €300 korting!

Jouw taak is om de maximale korting die Linday kan krijgen te bepalen.

Gevraagd

Programmeer een functie maximale_korting(prijzen) die gegeven een lijst met kostprijzen de maximale korting retourneert. Je mag ervan uitgaan dat de kostprijzen reeds gesorteerd werden.

Voorbeeld

>>> maximale_korting([100, 150, 200, 250, 300, 350, 400])
450

Bron

Gebaseerd op probleem Shopaholic, Universiteit van Valladolid (UVa).