Minecarts

Ο Steve έχει ~N~ βαγονέτα ορυχείου, αριθμημένα από ~1~ έως ~N~, τοποθετημένα σε μια σειρά πάνω σε μια γραμμή, από αριστερά προς τα δεξιά.

Αρχικά, υπάρχουν ~a_i~ πολύτιμοι λίθοι στο ~i~-οστό βαγονέτο.

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

Για να το πετύχει αυτό, σχεδιάζει να κατασκευάσει μια παράπλευρη γραμμή στα δεξιά όλων των βαγονέτων, η οποία διακλαδώνεται από την κύρια γραμμή. Ο Steve μπορεί να μετακινήσει βαγονέτα που βρίσκονται αριστερά της παράπλευρης γραμμής μέσα σε αυτήν, επιτρέποντας σε άλλα βαγονέτα που βρίσκονται αριστερά του να περάσουν από μπροστά του στην κύρια γραμμή.

Τα βαγονέτα που μετακινούνται στην παράπλευρη γραμμή μπορούν να επιστρέψουν στην κύρια γραμμή ένα-ένα: ένα βαγονέτο στην παράπλευρη γραμμή επιστρέφει στα αριστερά της παράπλευρης γραμμής και στα δεξιά όλων των άλλων βαγονέτων που βρίσκονται αριστερά της παράπλευρης γραμμής.

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

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

Παρακάτω φαίνεται ένα παράδειγμα ακολουθίας κινήσεων που μπορεί να πραγματοποιηθεί με ~5~ βαγονέτα, ξεκινώντας από την αρχική τους θέση:

Ο Steve έχει ~K~ επιπλέον πολύτιμους λίθους και μπορεί να τοποθετήσει οποιονδήποτε αριθμό από αυτούς στα βαγονέτα που είναι άδεια.

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

Για παράδειγμα, αν η παράπλευρη γραμμή είχε χωρητικότητα ~1~, δεν θα μπορούσαμε να πραγματοποιήσουμε τις κινήσεις στα παραπάνω διαγράμματα, οι οποίες απαιτούν χωρητικότητα τουλάχιστον ~2~.

Δεδομένου ότι ο Steve τοποθετεί τους επιπλέον πολύτιμους λίθους στα βαγονέτα με τον βέλτιστο τρόπο, ποια είναι η ελάχιστη χωρητικότητα της παράπλευρης γραμμής που πρέπει να κατασκευαστεί;

Είσοδος

Η πρώτη γραμμή εισόδου αποτελείται από δύο ακεραίους ~N~ και ~K~, χωρισμένους με κενό (~1 \le N \le 3 \times 10^5~, ~0 \le K \le 10^{12}~).

Η επόμενη γραμμή περιέχει ~N~ ακεραίους ~a_1,\ldots,a_N~ (~0 \le a_i \le 10^6~), όπου ο ~i~-οστός ακέραιος υποδεικνύει τον αριθμό των πολύτιμων λίθων στο ~i~-οστό βαγονέτο.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι ~15~ βαθμοί:

Βαθμοί	Όρια του ~N~	Όρια του ~K~
~2~	~1 \le N \le 5000~	~K = 0~
~2~	~1 \le N \le 5000~	~K = 10^{12}~
~2~	~1 \le N \le 5000~	~0 \le K \le 10^{12}~
~3~	~1 \le N \le 3 \times 10^5~	~K = 0~
~3~	~1 \le N \le 3 \times 10^5~	~K = 10^{12}~
~3~	~1 \le N \le 3 \times 10^5~	~0 \le K \le 10^{12}~

Έξοδος

Εκτυπώστε έναν ακέραιο, την ελάχιστη χωρητικότητα της παράπλευρης γραμμής που πρέπει να κατασκευαστεί, δεδομένου ότι ο Steve κατανέμει βέλτιστα έως και ~K~ επιπλέον πολύτιμους λίθους στα άδεια βαγονέτα.

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

input

4 14
5 0 4 0

output

1

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

Μια βέλτιστη κατανομή είναι να τοποθετήσουμε ~6~ από τους επιπλέον πολύτιμους λίθους στο βαγονέτο ~2~ και ~7~ από τους επιπλέον πολύτιμους λίθους στο βαγονέτο ~4~. Παρατηρήστε ότι αυτή η κατανομή δεν χρησιμοποιεί όλους τους διαθέσιμους πολύτιμους λίθους.

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

1. Μετακινούμε το βαγονέτο ~4~ πέρα από την παράπλευρη γραμμή.
2. Μετακινούμε το βαγονέτο ~3~ στην παράπλευρη γραμμή.
3. Μετακινούμε το βαγονέτο ~2~ πέρα από την παράπλευρη γραμμή.
4. Μετακινούμε το βαγονέτο ~1~ πέρα από την παράπλευρη γραμμή.
5. Μετακινούμε το βαγονέτο ~3~ έξω από την παράπλευρη γραμμή.
6. Μετακινούμε το βαγονέτο ~3~ πέρα από την παράπλευρη γραμμή.

input

4 8
5 0 4 0

output

2

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

Μια βέλτιστη κατανομή είναι να τοποθετήσουμε και τους ~8~ επιπλέον πολύτιμους λίθους στο βαγονέτο ~4~.

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

1. Μετακινούμε το βαγονέτο ~4~ πέρα από την παράπλευρη γραμμή.
2. Μετακινούμε το βαγονέτο ~3~ στην παράπλευρη γραμμή.
3. Μετακινούμε το βαγονέτο ~2~ στην παράπλευρη γραμμή.
4. Μετακινούμε το βαγονέτο ~1~ πέρα από την παράπλευρη γραμμή.
5. Μετακινούμε το βαγονέτο ~2~ έξω από την παράπλευρη γραμμή.
6. Μετακινούμε το βαγονέτο ~3~ έξω από την παράπλευρη γραμμή.
7. Μετακινούμε το βαγονέτο ~3~ πέρα από την παράπλευρη γραμμή.
8. Μετακινούμε το βαγονέτο ~2~ πέρα από την παράπλευρη γραμμή.

input

4 123456789
40 30 20 10

output

3

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

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

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

1. Μετακινούμε το βαγονέτο ~4~ στην παράπλευρη γραμμή.
2. Μετακινούμε το βαγονέτο ~3~ στην παράπλευρη γραμμή.
3. Μετακινούμε το βαγονέτο ~2~ στην παράπλευρη γραμμή.
4. Μετακινούμε το βαγονέτο ~1~ πέρα από την παράπλευρη γραμμή.
5. Μετακινούμε το βαγονέτο ~2~ έξω από την παράπλευρη γραμμή και στη συνέχεια πέρα από αυτήν.
6. Μετακινούμε το βαγονέτο ~3~ έξω από την παράπλευρη γραμμή και στη συνέχεια πέρα από αυτήν.
7. Μετακινούμε το βαγονέτο ~4~ έξω από την παράπλευρη γραμμή και στη συνέχεια πέρα από αυτήν.