22ος ΠΔΠ Καμπ (seniors)
Κατεστραμμένα λουλούδια (flowers)

Μια μέρα, ένας αγρότης άφησε τις \(N\) αγελάδες του (\(2 \leq N \leq 100.000\)) να βοσκάνε στο γρασίδι, όπως συνήθως. Όταν γύρισε, τις βρήκε όμως να τρώνε τα λουλούδια του κήπου του! Θέλοντας να ελαχιστοποιήσει τη ζημιά που θα γίνει από δω και πέρα, ο αγρότης αποφάσισε να μεταφέρει αμέσως κάθε αγελάδα πίσω στο στάβλο.

Κάθε αγελάδα \(i\) είναι σε μια θέση που απέχει \(T_i\) λεπτά (\(1 \leq T_i \leq 2.000.000\)) από το στάβλο, και καταστρέφει \(D_i\) (\(1 \leq D_i \leq 100\)) λουλούδια το λεπτό. Όσο και να προσπαθήσει, ο αγρότης μπορεί να μεταφέρει μόνο μία αγελάδα κάθε φορά. Η μεταφορά της αγελάδας \(i\) απαιτεί συνολικά \(2 \cdot T_i\) λεπτά (\(T_i\) για να την πάει ο αγρότης στο στάβλο και \(T_i\) για να επιστρέψει).

Ο αγρότης ξεκινά από τον κήπο, μεταφέρει μία αγελάδα στο στάβλο, επιστρέφει και αμέσως μεταφέρει την επόμενη αγελάδα.

Πρόβλημα

Γράψτε ένα πρόγραμμα που θα βρίσκει τη σειρά με την οποία ο αγρότης πρέπει να μεταφέρει τις αγελάδες, ώστε να καταστραφεί το ελάχιστο δυνατό πλήθος λουλουδιών.

Αρχείο εισόδου

Γραμμή \(1\): περιέχει τον ακέραιο \(N\).

Γραμμές \(2 \ldots N+1\): κάθε μία περιέχει δύο ακέραιους χωρισμένους με κενά διαστήματα, \(T_i\) και \(D_i\), που περιγράφουν τα χαρακτηριστικά της αγελάδας \(i\).

Αρχείο εξόδου

Γραμμή \(1\): περιέχει έναν μόνο αριθμό, το ελάχιστο πλήθος των κατεστραμμένων λουλουδιών.

Παράδειγμα Αρχείων Εισόδου - Εξόδου:

flowers.in	flowers.out
6 3 1 2 5 2 3 3 2 4 1 1 6	86

Περιορισμοί