Μπισκότα (biscuits) Η θεία Khong οργανώνει ένα πάρτυ με ~x~ συμμετέχοντες, και θέλει να δώσει στον καθένα ένα πακέτο με μπισκότα. Υπάρχουν ~k~ διαφορετικοί τύποι μπισκότων, αριθμημένοι από ~0~ μέχρι και ~k - 1~. Κάθε μπισκότο τύπου ~i~ (~0 \le i \le k - 1~) έχει γευστική αξία ίση με ~2^i~. Η θεία Khong έχει ~a[i]~ (πιθανόν και μηδέν) μπισκότα τύπου ~i~ στη διάθεσή της.

Κάθε πακέτο της θείας Khong θα περιέχει μηδέν ή περισσότερα μπισκότα κάθε τύπου. Ο συνολικός αριθμός των μπισκότων τύπου ~i~ σε όλα τα πακέτα δεν πρέπει να υπερβαίνει το ~a[i]~. Το άθροισμα των γευστικών αξιών όλων των μπισκότων ενός πακέτου ονομάζεται συνολική γευστικότητα του πακέτου.

Βοηθήστε τη θεία Khong να βρει το πλήθος των διαφορετικών τιμών ~y~, τέτοιων ώστε να είναι δυνατόν να φτιαχθούν ~x~ πακέτα, που καθένα να έχει συνολική γευστικότητα ίση με ~y~.

Λεπτομέρειες υλοποίησης

Πρέπει να υλοποιήσετε την παρακάτω συνάρτηση:

int64 count_tastiness(int64 x, int64[] a)

• ~x~: το πλήθος των πακέτων μπισκότων που θα φτιαχθούν.
• ~a~: ένας πίνακας μήκους ~k~. Για ~0 \le i \le k - 1~, το ~a[i]~ είναι το πλήθος των μπισκότων τύπου ~i~ που έχει στη διάθεσή της η θεία.
• Η συνάρτηση πρέπει να επιστρέφει το πλήθος των διαφορετικών τιμών ~y~, έτσι ώστε η θεία να μπορεί να φτιάξει ~x~ πακέτα μπισκότων, που καθένα να έχει συνολική γευστικότητα ~y~.
• Η συνάρτηση καλείται συνολικά ~q~ φορές (βλ. τις παραγράφους Περιορισμοί και Υποπροβλήματα για τις επιτρεπόμενες τιμές του ~q~). Κάθε μια από αυτές τις κλήσεις θα πρέπει να αντιμετωπίζεται σαν ένα διαφορετικό σενάριο.

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

Παράδειγμα 1

Έστω η παρακάτω κλήση:

count_tastiness(3, [5, 2, 1])

Αυτό σημαίνει ότι η θεία θέλει να συσκευάσει ~3~ πακέτα, και υπάρχουν ~3~ τύποι μπισκότων στη διάθεσή της:

• ~5~ μπισκότα τύπου ~0~, με τιμή γευστικότητας ~1~ το καθένα,
• ~2~ μπισκότα τύπου ~1~, με τιμή γευστικότητας ~2~ το καθένα,
• ~1~ μπισκότο τύπου ~2~, με τιμή γευστικότητας ~4~.

Οι δυνατές τιμές του ~y~ είναι ~[0, 1, 2, 3, 4]~. Για παράδειγμα για να φτιάξει ~3~ πακέτα συνολικής γευστικότητας ~3~ το καθένα, η θεία μπορεί να συσκευάσει:

• ένα πακέτο που να περιέχει τρία μπισκότα τύπου ~0~, και
• δύο πακέτα που καθένα να περιέχει ένα μπισκότο τύπου ~0~ και ένα μπισκότο τύπου ~1~.

Εφόσον υπάρχουν ~5~ δυνατές τιμές του ~y~, η συνάρτηση πρέπει να επιστρέψει 5.

Παράδειγμα 2

Έστω η παρακάτω κλήση:

count_tastiness(2, [2, 1, 2])

Αυτό σημαίνει ότι η θεία θέλει να συσκευάσει ~2~ πακέτα, και υπάρχουν ~3~ τύποι μπισκότων στη διάθεσή της:

• ~2~ μπισκότα τύπου ~0~, με τιμή γευστικότητας ~1~ το καθένα,
• ~1~ μπισκότο τύπου ~1~, με τιμή γευστικότητας ~2~,
• ~2~ μπισκότα τύπου ~2~, με τιμή γευστικότητας ~4~ το καθένα.

Οι δυνατές τιμές του ~y~ είναι ~[0, 1, 2, 4, 5, 6]~. Εφόσον υπάρχουν ~6~ δυνατές τιμές του ~y~, η συνάρτηση πρέπει να επιστρέψει ~6~.

Περιορισμοί

• ~1 \le k \le 60~
• ~1 \le q \le 1\,000~
• ~1 \le x \le 10^18~
• ~0 \le a[i] \le 10^18~ (για κάθε ~0 \le i \le k - 1~)
• Για κάθε κλήση της count_tastiness, το άθροισμα των τιμών γευστικότητας όλων των μπισκότων που είναι στη διάθεση της θείας δεν ξεπερνάει το ~10^18~.

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

1. (~9~ βαθμοί) ~q \le 10~, και για κάθε κλήση της count_tastiness, το άθροισμα των τιμών γευστικότητας όλων των μπισκότων που είναι στη διάθεση της θείας δεν ξεπερνάει το ~100\,000~.
2. (~12~ βαθμοί) ~x = 1~, ~q \le 10~
3. (~21~ βαθμοί) ~x \le 10\,000~, ~q \le 10~
4. (~35~ βαθμοί) Η σωστή τιμή που επιστρέφεται σε κάθε κλήση της count_tastiness δεν ξεπερνά το ~200\,000~.
5. (~23~ βαθμοί) Χωρίς επιπλέον περιορισμούς.

Υποδειγματικός βαθμολογητής

Ο υποδειγματικός βαθμολογητής διαβάζει την είσοδο ως εξής: Η πρώτη γραμμή περιέχει έναν ακέραιο ~q~. Μετά από αυτό, ακολουθούν ~q~ ζεύγη γραμμών, και κάθε ζεύγος περιγράφει ένα σενάριο με την εξής μορφή:

• γραμμή ~1~: ~k~ ~x~
• γραμμή ~2~: ~a[0]~ ~a[1] ... a[k - 1]~

Η έξοδος του υποδειγματικού βαθμολογητή είναι ως εξής:

• γραμμή ~i~ (~1 \le i \le q~): η τιμή επιστροφής της count_tastiness για το ~i~-οστό σενάριο της εισόδου.