Asteroid Miner

Βρισκόμαστε στο έτος ~2217~ και ο Ryan είναι ένας εξορύκτης αστεροειδών. Βγάζει τα προς το ζην εξορύσσοντας αστεροειδείς και πουλώντας τους στο CCO (Celestial Cargo Outpost).

Στην τελευταία του αποστολή εξόρυξης, εξόρυξε ~N~ κομμάτια ορυκτών, όπου το ~i~-οστό κομμάτι έχει αξία ~v_i~ και μάζα ~m_i~. Ο Ryan σχεδιάζει να μεταφέρει ένα σύνολο από αυτά τα κομμάτια στο CCO με τον πύραυλό του, αλλά έχει καύσιμα μόνο για ένα ακόμη ταξίδι. Υπολόγισε ότι η μέγιστη συνολική μάζα που μπορεί να μεταφέρει με ασφάλεια ο πύραυλός του είναι ~M~.

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

Βοηθήστε τον Ryan να βρει τη μέγιστη συνολική αξία που μπορεί να μεταφέρει στο CCO, τηρώντας τους περιορισμούς του πυραύλου του.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο ακέραιους αριθμούς, χωρισμένους με κενό: ~N~ (~1 \le N \le 500.000~) και ~M~ (~1 \le M \le 10^{12}~).

Καθεμία από τις επόμενες ~N~ γραμμές θα περιέχει δύο ακέραιους αριθμούς, χωρισμένους με κενό: ~v_i~ (~1 \le v_i \le 10^{12}~) και ~m_i~ (~1 \le m_i \le 10^{12}~), οι οποίοι αντιστοιχούν στην αξία και τη μάζα του ~i~-οστού κομματιού ορυκτού, αντίστοιχα.

Επιπλέον, για οποιαδήποτε δύο κομμάτια ορυκτών ~i,j~ (~1 \le i,j \le N~), ισχύει είτε ~m_i \mid m_j~ είτε ~m_j \mid m_i~, όπου ~a \mid b~ σημαίνει ότι το ~a~ είναι διαιρέτης του ~b~ (δηλαδή το ~\frac{b}{a}~ είναι ακέραιος).

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

Βαθμοί	Όρια του ~N~	Όρια του ~M~	Επιπλέον περιορισμοί
~2~	~N = 2~	~1 \le M \le 10^4~	Κανένας επιπλέον περιορισμός.
~2~	~1 \le N \le 20~	~1 \le M \le 10^4~	Κανένας επιπλέον περιορισμός.
~4~	~1 \le N \le 1000~	~1 \le M \le 10^4~	Κανένας επιπλέον περιορισμός.
~6~	~1 \le N \le 1000~	~1 \le M \le 10^8~	Κανένας επιπλέον περιορισμός.
~2~	~1 \le N \le 500.000~	~1 \le M \le 10^8~	Όλες οι τιμές ~m_i~ είναι ίσες.
~3~	~1 \le N \le 500.000~	~1 \le M \le 10^8~	Υπάρχουν το πολύ δύο διαφορετικές τιμές ~m_i~.
~6~	~1 \le N \le 500.000~	~1 \le M \le 10^{12}~	Κανένας επιπλέον περιορισμός.

Έξοδος

Σε μία γραμμή, να εξάγετε έναν ακέραιο αριθμό: τη μέγιστη συνολική αξία που μπορεί να μεταφέρει ο Ryan στο CCO.

Παράδειγμα

input

6 10
1 1
5 2
200 6
9 2
6 2
100 1

output

310

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

Ο Ryan μπορεί να πάρει όλα τα κομμάτια εκτός από το δεύτερο και το πέμπτο, πετυχαίνοντας συνολική αξία ~1 + 200 + 9 + 100 = 310~.

Σημείωσε ότι η συνολική μάζα των κομματιών είναι ~1 + 6 + 2 + 1 = 10~. Μπορούμε να αποδείξουμε ότι αυτή είναι η βέλτιστη επιλογή.