Rainy Markets

Υπάρχουν ~N~ στεγασμένες στάσεις λεωφορείων, αριθμημένες από ~1,\ldots,N~. Η ~i~-οστη στάση λεωφορείου μπορεί να χωρέσει ~B_i~ άτομα μέσα.

Για κάθε ~i \in~ {~1,\ldots,N-1~}, υπάρχει ένα πεζοδρόμιο που συνδέει τη στάση ~i~ με την στάση ~i + 1~, με μια υπαίθρια αγορά στη μέση. Η ~i~-οστη αγορά έχει ~U_i~ ομπρέλες προς πώληση, με κάθε μια να κοστίζει ~$1~.

Αυτή τη στιγμή, η ~i~-οστη αγορά έχει ~P_i~ άτομα μέσα και όλα τα άτομα βρίσκονται σε μια αγορά, οπότε όλες οι στάσεις λεωφορείου είναι άδειες.

Ξαφνικά, ξεκινάει να βρέχει και όλοι όσοι βρίσκονται στην αγορά ~i~ πρέπει να διαλέξουν ανάμεσα σε τρεις επιλογές:

  ● Να πάνε στην στάση λεωφορείου ~i~

  ● Να πάνε στη στάση λεωφορείου ~i+1~ ή

  ● Να μείνουν και να αγοράσουν μια ομπρέλα.

Εαν ένα άτομο δεν καταφέρει να βρει μια θέσει σε κάποια στάση λεωφορείου ή να αγοράσει μια ομπρέλα, θα βραχεί.

Εαν όλοι συντονιστούν με τον βέλτιστο τρόπο, μπορούν να παραμείνουν όλοι στεγνοί; Αν ναι, ποιό είναι το λιγότερο δυνατό ποσό χρημάτων που χρειάζεται να ξοδέψουν και σε ποιά στάση λεωφορείου πρέπει να κατευθυνθεί το κάθε άτομο;

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει το ~N~.

Η δεύτερη γραμμή της εισόδου περιέχει ~N~ χωρισμένους με κενό ακέραιους αριθμούς ~B_i (1 \le i \le N)~, την χωριτικότητα της στάσης λεωφορείου ~i~.

Η τρίτη γραμμή της εισόδου περιέχει ~N-1~ χωρισμένους με κενό ακέραιους αριθμούς ~P_i (1 \le i \le N-1)~, τον αριθμό των ατόμων στην αγορά ~i~.

Η τέταρτη γραμμή της εισόδου περιέχει ~N-1~ χωρισμένους με κενό ακέραιους αριθμούς ~U_i (1 \le i \le N-1)~, τον αριθμό των ομπρελών προς πώληση στην αγορά ~i~.

Βαθμολογία

Βαθμοί	Αριθμός στάσεων λεωφορείων	Μέγιστος αριθμός ατόμων/στάση λεωφορείου	Μέγιστος αριθμός ατόμων/αγορά	Μέγιστος αριθμός ομπρελών/αγορά
5	~2 \le N \le 10^6~	~0 \le B_i \le 2 \cdot 10^9~	~0 \le P_i \le 10^9~	~U_i = 0~
5	~2 \le N \le 2\,000~	~0 \le B_i \le 400~	~0 \le P_i \le 200~	~0 \le U_i \le 200~
6	~2 \le N \le 4\,000~	~0 \le B_i \le 4\,000~	~0 \le P_i \le 2\,000~	~0 \le U_i \le 2\,000~
9	~2 \le N \le 10^6~	~0 \le B_i \le 2 \cdot 10^9~	~0 \le P_i \le 10^9~	~0 \le U_i \le 10^9~

Έξοδος

Εαν κάθε άτομο μπορεί να μείνει στεγνό είτε κάτω από μια ομπρέλα είτε σε μια στάση λεωφορείου, η έξοδος θα είναι ~N + 1~ γραμμές:

  ● Η πρώτη γραμμή θα περιέχει τη λέξη YES.

  ● Η δεύτερη γραμμή θα περιέχει το λιγότερο ποσό χρημάτων που χρειάζεται να ξοδευτούν σε ομπρέλες.

  ● Οι επόμενες ~N - 1~ γραμμές θα περιέχουν η καθεμια τρεις ακέραιους αριθμούς χωρισμένους με κενό:

    - Τον αριθμό των ατόμων στην αγορά ~i~ που κατευθύνονται προς τη στάση ~i~

    - Τον αριθμό των ατόμων στην αγορά ~i~ που αγοράζουν μια ομπρέλα

    - Τον αριθμό των ατόμων στην αγορά ~i~ που κατευθύνονται προς τη στάση ~i+1~

   Όπου ~1 \le i \le N-1~.

Εαν δεν μπορούν όλοι να μείνουν στεγνοί, η έξοδος θα είναι μια γραμμή που θα περιέχει τη λέξη NO.

Αν υπάρχουν πολλαπλές πιθανές σωστές έξοδοι, οποιαδήποτε σωστή έξοδος θα γίνει δεκτή.

Παραδείγματα

input

3
10 15 10
20 20
0 0

output

NO

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

Υπάρχουν 35 διαθέσιμες θέσεις στις στάσεις λεωφορείων και καμία διαθέσιμη ομπρέλα, αλλά υπάρχουν 40 άτομα στις αγορές.

input

3
10 15 10
20 20
0 11

output

YES
5
10 0 10
5 5 10

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

Κοιτάζοντας την αγορά ~1~, 10 άτομα θα πάνε στην στάση ~1~, κανένας δεν θα αγοράσει ομπρέλα και 10 άτομα θα πάνε στη στάση ~2~.

Κοιτάζοντας την αγορά ~2~, 5 άτομα θα πάνε στη στάση ~2~, 5 άτομα θα μείνουν και θα αγοράσουν μια ομπρέλα και 10 άτομα θα κατευθυνθούν προς την στάση ~3~.

Συνολικά αγοράστηκαν 5 ομπρέλες, οι οποίες κοστίζουν ~$5~.