Data Centers

Η GoncaSoft είναι μια εταιρεία στο διαδίκτυο που χρησιμοποιεί πολλές υπηρεσίες (services) και έχει ~n~ κέντρα εξυπηρέτησης (data centers) σε όλον τον κόσμο. Κάθε κέντρο εξυπηρέτησης έχει έναν αριθμό από υπολογιστές. Για λόγους ασφαλείας και εφεδρικότητας, ένα ή περισσότερα αντίγραφα κάθε υπηρεσίας εκτελούνται ταυτόχρονα. Κάθε αντίγραφο τρέχει σε διαφορετικό κέντρο εξυπηρέτησης και απαιτεί έναν αριθμό υπολογιστών για να εκτελεστεί. Όλα τα αντίγραφα κάθε μιας υπηρεσίας, απαιτούν τον ίδιο αριθμό υπολογιστών.

Όταν η GoncaSoft σχεδιάζει την δημιουργία μιας νέας υπηρεσίας ~i~ που απαιτεί ~c_i~ αντίγραφα, κάθε ένα από τα οποία απαιτεί ~m_i~ υπολογιστές, ταξινομεί τα κέντρα εξυπηρέτησης σε φθίνουσα σειρά με τον τρέχοντα αριθμό ελεύθερων υπολογιστών και μετά χρησιμοποιεί ~m_i~ υπολογιστές από τα πρώτα ~c_i~ κέντρα εξυπηρέτησης.

Παρακαλώ υπολογίστε τους υπολειπόμενους ελεύθερους υπολογιστές στα κέντρα εξυπηρέτησης, αφού δημιουργηθούν ~s~ υπηρεσίες με τη δεδομένη σειρά.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακεραίους, χωρισμένους με κενό, ~n~ και ~s~, που αναπαριστούν τον αριθμό των κέντρων εξυπηρέτησης που έχει η GoncaSoft και τον αριθμό των νέων υπηρεσιών που η GoncaSoft θα δημιουργήσει.

Η επόμενη γραμμή περιέχει ~n~ ακεραίους χωρησμένους με κενά που αναπαριστούν τον αριθμό των διαθέσιμων αριθμών καθενός από τα ~n~ κέντρα εξυπηρέτησης, πριν δημιουργηθούν εργασίες.

Οι επόμενες ~s~ γραμμές περιγράφουν τις διεργασίες που θα δημιουργηθούν: η ~i~-oστή γραμμή περιέχει δύο ακεραίους ~m_i~ και ~c_i~, χωρισμένους με κενό, που αναπαριστούν τον αριθμό των υπολογιστών και τον αριθμό των αντιγράφων που απαιτεί η ~i~-oστή υπηρεσία.

Έξοδος

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

Περιορισμοί

• ~1 \le n \le 100\,000~ και ~0 \le s \le 5\,000~.
• Κάθε κέντρο εξυπηρέτησης έχει το πολύ ~10^9~ υπολογιστές αρχικά.
• ~1 \le m_i \le 10^9~, για κάθε υπηρεσία ~i~ με ~1 \le i \le s~.
• ~1 \le c_i \le\le n~, για κάθε υπηρεσία ~i~ με ~1 \le i \le s~.
• Τα κέντρα εξυπηρέτησης θα έχουν πάντα αρκετούς υπολογιστές για όλες τις διεργασίες.

Βαθμολόγηση

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~12~	~n \le 100, s = 0~
~2~	~12~	~n \le 100, s \le 10~
~3~	~9~	~n \le 50\,000, s \le 100~
~4~	~26~	Κάθε κέντρο εξυπηρέτησης έχει το πολύ ~1\,000~ υπολογιστές.
~5~	~18~	~c_i = 1~, για όλες τις υπηρεσίες, από την ~1~ έως την ~s~.
~6~	~23~	Κανένας επιπλέον περιορισμός.

Παράδειγμα

input

5 4
20 12 10 15 18
3 4
4 1
1 3
4 2

output

11 10 10 9 8

Επεξήγηση του παραδείγματος:

Βήμα	Διαθέσιμοι υπολογιστές	Λειτουργίες
Έναρξη	~20\,12\,10\,15\,18~	-
Υπηρεσία #1: πριν την εκτέλεση.	~20\,18\,15\,12\,10~	Ταξινόμηση κέντρων εξυπηρέτησης σε φθίνουσα σειρά ελεύθερων υπολογιστών.
Υπηρεσία #1: μετά την εκτέλεση.	~17\,15\,12\,9\,10~	Χρησιμοποιήθηκαν ~3~ υπολογιστές από κάθε ένα από τα ~4~ πρώτα κέντρα εξυπηρέτησης.
Υπηρεσία #2: πριν την εκτέλεση.	~17\,15\,12\,10\,9~	Ταξινόμηση κέντρων εξυπηρέτησης σε φθίνουσα σειρά ελεύθερων υπολογιστών.
Υπηρεσία #2: μετά την εκτέλεση.	~13\,15\,12\,10\,9~	Χρησιμοποιήθηκαν ~4~ υπολογιστές από το πρώτο κέντρο εξυπηρέτησης.
Υπηρεσία #3: πριν την εκτέλεση.	~15\,13\,12\,10\,9~	Ταξινόμηση κέντρων εξυπηρέτησης σε φθίνουσα σειρά ελεύθερων υπολογιστών.
Υπηρεσία #3: μετά την εκτέλεση.	~14\,12\,11\,10\,9~	Χρησιμοποιήθηκε ~1~ υπολογιστής από κάθε ένα από τα ~3~ πρώτα κέντρα εξυπηρέτησης.
Υπηρεσία #4: πριν την εκτέλεση.	~14\,12\,11\,10\,9~	Ταξινόμηση κέντρων εξυπηρέτησης σε φθίνουσα σειρά ελεύθερων υπολογιστών.
Υπηρεσία #4: μετά την εκτέλεση.	~10\,8\,11\,10\,9~	Χρησιμοποιήθηκαν ~4~ υπολογιστές από κάθε ένα από τα ~2~ πρώτα κέντρα εξυπηρέτησης.
Τέλος	~11\,10\,10\,9\,8~	Ταξινόμηση κέντρων εξυπηρέτησης σε φθίνουσα σειρά ελεύθερων υπολογιστών.