Alkatrészeket gyártó üzem N megrendelést kapott. Minden megrendelésre tudja, hogy mennyi idő szükséges az alkatrész legyártásához. Az üzemnek van legalább N munkagépe, így minden alkatrészt külön gépen tud legyártani. A gyártás előtt minden alkatrészt elő kell készíteni, de ezt az elő- készítést csak egy gép tudja végezni. Az is ismert, hogy az egyes alkatrészek előkészítése mennyi időt igényel. Minden alkatrész előkészítése után azonnal elkezdődik a gyártása.

Készíts programot, amely megadja, hogy milyen sorrendben kell előkészíteni az alkatrészeket, hogy az összes legyártása a leghamarabb befejeződjön!

A standard bemenet első sora az alkatrészek számát tartalmazza (1≤N≤30 000). A második és a harmadik sor pontosan N egész számot tartalmaz egy-egy szóközzel elválasztva. A második sor i-edik eleme az i-edik alkatrész előkészítési ideje, a harmadik sor i-edik eleme pedig az alkatrész legyártásához szükséges idő. A második és harmadik sorban minden szám értéke legfeljebb 1000. 

A standard kimenet első sorába az összes alkatrész legyártásához szükséges minimális időt kell írni! A második sor az alkatrészek sorszámainak egy olyan felsorolását tartalmazza (egy-egy szóközzel elválasztva) amely a legkorábbi befejezést biztosítja! Több megoldás esetén bármelyik megadható.

Bemenet	Kimenet
3 1 3 3 4 1 5	8 3 1 2

A feladat forrása: mester.inf.elte.hu, Haladó > Mohó algoritmusok > Alkatrészgyártás

Algoritmusok: mohó algoritmus

megoldás