Εξωγήινες συχνότητες (aliens)

Είμαστε στο έτος 2026 και επιτέλους έχει ανακαλυφθεί ένας ραδιοφωνικός πομπός που μπορεί να στέλνει σήματα σε εξωγήινους! Δυστυχώς, δεν είναι γνωστή η ακριβής συχνότητα στην οποία λειτουργούν οι εξωγήινοι δέκτες. Έστω ότι οι συχνότητες είναι φυσικοί αριθμοί που δεν υπερβαίνουν το ~10^9~. Είναι γνωστό ότι η σωστή συχνότητα είναι μία από ~N~ δεδομένες συχνότητες ~f_i~ (~1 \le i \le N~) σε αυτό το διάστημα, οπότε οι επιστήμονες πρέπει να στείλουν ένα μήνυμα σε κάθε μία από αυτές για να είναι βέβαιοι ότι οι εξωγήινοι θα το λάβουν.

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

• Να αυξηθεί ή να μειωθεί η συχνότητα κατά 1. Στην περίπτωση αυτή, ο πομπός υπερφορτίζεται και η θερμοκρασία του πομπού αυξάνει κατά 1 βαθμό Κελσίου. Η πράξη αυτή απαιτεί 1 δευτερόλεπτο για να εκτελεστεί.
• Να αυξηθεί ή να μειωθεί η συχνότητα κατά 2. Στην περίπτωση αυτή, η θερμοκρασία του πομπού δεν μεταβάλλεται, αλλά η πράξη αυτή απαιτεί 2 δευτερόλεπτα για να εκτελεστεί.

Ο πομπός λειτουργεί κάπου στην Ανταρκτική και η αρχική του θερμοκρασία είναι 0 βαθμοί Κελσίου. Αν η θερμοκρασία του υπερβεί τους ~T~ βαθμούς, τότε ο πομπός καταστρέφεται. Αυτό δεν πρέπει να συμβεί γιατί ο πομπός είναι πανάκριβος.

Γράψτε ένα πρόγραμμα που να υπολογίζει τον ελάχιστο χρόνο που απαιτείται για να εκπέμψουν οι επιστήμονες σε όλες τις ~N~ δοθείσες συχνότητες. Θεωρήστε ότι η εκπομπή ενός μηνύματος δεν απαιτεί χρόνο (μόνο η αύξηση ή η μείωση της συχνότητας του πομπού).

Δεδομένα εισόδου

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

Δεδομένα εξόδου

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

Παράδειγμα εισόδου και εξόδου

Είσοδος     Έξοδος
4 2
3 5 6 9     12

Εξήγηση: Με μία δυνατή ακολουθία πράξεων, ο πομπός μπορεί να περάσει διαδοχικά από τις εξής συχνότητες: ~0,2,3,5,7,9,8,60,2,3,5,7,9,8,6~. (Οι αντίστοιχες πράξεις ήταν ~+2,+1,+2,+2,+2,-1,-2+2,+1,+2,+2,+2,-1,-2~). Στο τέλος της, η θερμοκρασία του πομπού είναι 22. Η ακολουθία αυτή περνά από όλες τις δοθείσες συχνότητες και απαιτεί 12 δευτερόλεπτα. Δεν υπάρχει τρόπος να επιτευχθεί ο σκοπός σε λιγότερα από 12 δευτερόλεπτα.

Περιορισμοί

• Mέγιστος χρόνος εκτέλεσης: 2 sec.
• Mέγιστη διαθέσιμη μνήμη: ~64 \;\rm MB~.

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

• Σε testcases που θα αντιστοιχούν στο 25% της βαθμολογίας, θα είναι ~N \le 10,T \le 10~.
• Σε testcases που θα αντιστοιχούν στο 50% της βαθμολογίας, θα είναι ~N \le 100,T \le 100~.
• Σε testcases που θα αντιστοιχούν στο 100% της βαθμολογίας, θα είναι ~N \le 5.000,T \le 5.000~.