Πρόσληψη Πιτσαδόρων

Ο Τάκης το πήρε τελικά απόφαση να προσλάβει εργαζόμενους. Μάλιστα, έχει βρει ~N~ υποψήφιους πιτσαδόρους. Κάθε υποψήφιος μπορεί να προσληφθεί με το πολύ ένα είδος συμβολαίου: χάλκινο, ασημένιο ή χρυσό. Ο προϋπολογισμός του Τάκη του επιτρέπει να προσφέρει μέχρι ~X~ χάλκινα, μέχρι ~Y~ ασημένια και μέχρι ~Z~ χρυσά συμβόλαια. Επιπλέον, ο ίδιος έχει φροντίσει να ισχύει ότι ~X + Y + Z \ge N~.

Ανάλογα με το συμβόλαιο που λαμβάνει ένας πιτσαδόρος αποδίδει διαφορετικά. Αν στον ~i~-οστο πιτσαδόρο προσφερθεί χάλκινο συμβόλαιο αυτός θα έχει απόδοση ~A_i~, αν του προσφερθεί ασημένιο θα έχει απόδοση ~B_i~ και αν του προσφερθεί χρυσό θα έχει απόδοση ~C_i~. Για όλους τους υποψηφίους ισχύει ότι ~A_i \le B_i \le C_i~, δηλαδή όταν προσφέρουμε συμβόλαιο υψηλότερης βαθμίδας η απόδοση πάντα βελτιώνεται.

Προφανώς, ο Τάκης θέλει να μεγιστοποιήσει την συνολική απόδοση των πιτσαδόρων του, δηλαδή το άθροισμα των αποδόσεων τους. Παρόλα αυτά, είναι απαραίτητο να παραμείνει εντός προϋπολογισμού. Να βρείτε την μέγιστη συνολική απόδοση που μπορεί να πετύχει ο Τάκης, τηρώντας τα όρια που έχει θέσει για κάθε είδος συμβολαίου.

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο hiring.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο hiring.out.

Αρχεία εισόδου (hiring.in)

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει τέσσερις ακέραιους αριθμούς ~N~, ~X~, ~Y~ και ~Z~, χωρισμένους ανά δύο με ένα κενό διάστημα: το πλήθος των υποψηφίων, το μέγιστο πλήθος χάλκινων συμβολαίων, το μέγιστο πλήθος ασημένιων συμβολαίων και το μέγιστο πλήθος χρυσών συμβολαίων. Ακολουθούν ~N~ γραμμές καθεμία από τις οποίες αποτελείται από τρεις ακέραιους αριθμούς ~A_i~, ~B_i~ και ~C_i~, χωρισμένους ανά δύο με ένα κενό διάστημα: την απόδοση του ~i~-οστου υποψηφίου αν του προσφερθεί χάλκινο, ασημένιο ή χρυσό συμβόλαιο, αντίστοιχα.

Αρχεία εξόδου (hiring.out)

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την μέγιστη συνολική απόδοση που μπορεί να πετύχει ο Τάκης αν προσφέρει μέχρι ~X~ χάλκινα, μέχρι ~Y~ ασημένια και μέχρι ~Z~ χρυσά συμβόλαια.

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

Είσοδος:

1
5 3 1 1
3 6 8
1 1 2
4 9 12
3 5 7
9 9 9

Έξοδος:

31

Εξήγηση: Η καλύτερη επιλογή πιτσαδόρων είναι να δώσουμε ασημένιο συμβόλαιο στον πρώτο (απόδοση ~6~), χάλκινο στον δεύτερο (απόδοση ~1~), χρυσό στον τρίτο (απόδοση ~12~), χάλκινο στον τέταρτο (απόδοση ~3~) και χάλκινο στον πέμπτο (απόδοση ~9~). Η συνολική απόδοση έτσι είναι ~6 + 1 + 12 + 3 + 9 = 31~.

Υποπροβλήματα:

1. (8 βαθμοί) ~N \le 14~
2. (24 βαθμοί) ~Z = 0~
3. (3 βαθμοί) ~X = 0~
4. (12 βαθμοί) ~A_1 = A_2 = ... = A_N~ (οι αποδόσεις των χάλκινων συμβολαίων είναι όλες ίσες), ~B_1 \le B_2 \le ... \le B_N~ (οι αποδόσεις των ασημένιων συμβολαίων βρίσκονται σε αύξουσα σειρά) και ~C_1 \ge C_2 \ge ... \ge C_N~ (οι αποδόσεις των χρυσών συμβολαίων βρίσκονται σε φθίνουσα σειρά)
5. (20 βαθμοί) ~Z = 1~
6. (33 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

Περιορισμοί

• ~1 \le N \le 100.000~
• ~0 \le X,\; Y,\; Z \le N~
• ~X + Y + Z \ge N~
• ~1 \le A_i \le B_i \le C_i \le 1.000.000.000~

Παρατηρήσεις

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~64~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: hiring *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: hiring */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: hiring */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: hiring */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.