Fișierul intrare/ieșire	freelancing.in, freelancing.out	Sursă	Concurs IQ Academy | Clasa a 10-a
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.07 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Freelancing (clasa a 10-a)

După cum reiese și din numele problemei, broscuța Bixi s-a decis să încerce acest nou fenomen din lumea IT. Ea are o listă de N sarcini de îndeplinit pentru diverși clienți. Fiecare sarcină are un termen limită și un profit. Ea poate executa o singură sarcină la un moment de timp, iar fiecare sarcină executată îi va ocupa o întreagă unitate de timp.

Cerință

Bixi vrea să își achiziționeze cât mai repede o frunză pe care să poată locui în celebrul lac Lixi. Cum frunzele sunt scumpe, ea vrea să știe ce sarcini trebuie să execute astfel încât să obțină un profit maxim.

Date de intrare

Fișierul de intrare freelancing.in conține pe prima linie N, numărul de sarcini. Pe următoarele N linii se vor găsi câte două numere naturale T[i] și P[i], reprezentând termenul limită și profitul sarcinii cu indexul i.

Date de ieșire

Fișierul de ieșire freelancing.out conține pe prima linie un număr natural reprezentând profitul maxim, iar pe cea de-a doua linie indecșii sarcinilor care trebuie executate pentru obținerea acestui profit.

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ T[i] ≤ 50.000, 1 ≤ i ≤ N
• 1 ≤ P[i] ≤ 1.000, 1 ≤ i ≤ N
• Chiar dacă lucrează în IT, Bixi își începe munca în unitatea de timp 1.
• Bixi încasează profitul pe o sarcină doar dacă o termină cel târziu în momentul de timp egal cu termenul limită al acesteia.
• Dacă sunt mai multe soluții care obțin profit maxim, se poate afișa oricare dintre acestea.
• Indecșii sarcinilor pot fi afișați în orice ordine.

Exemplu