Kuhar

Η Liza εργάζεται ως σερβιτόρα σε ένα εστιατόριο. Απόψε είναι τα γενέθλιά της και η Liza ζήτησε από τον σεφ να ετοιμάσει τα ξεχωριστό γεύμα του για τους φίλους της. Το γεύμα του σεφ αποτελείται από ~N~ συστατικά. Για να ετοιμάσει μια μερίδα από το γεύμα χρειάζεται μια συγκεκριμένη ποσότητα από κάθε συστατικό.

Υπάρχουν ήδη κάποια υλικά διαθέσιμα στην κουζίνα και η Liza θα αγοράσει τα υπόλοιπα στο παντοπωλείο. Το κατάστημα διαθέτει όλα τα απαραίτητα υλικά, το καθένα έρχεται σε μικρότερες και μεγαλύτερες συσκευασίες. Η Liza έχει ~M~ δολάρια και θέλει να τα ξοδέψει ώστε ο σεφ να μπορεί να παρασκευάσει τις περισσότερες μερίδες του γεύματός του.

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους ~N~ και ~M, 1 \le N \le 100,\,1 \le M \le 100\,000~.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει ~6~ θετικούς ακέραιους αριθμούς, πληροφορίες για ένα συστατικό. Αυτά προσδιορίζουν, με τη σειρά:

• ~X, 10 \le X \le 100~, η ποσότητα του συστατικού που απαιτείται σε μία μερίδα,
• ~Y, 1 \le Y \le 100~, η ποσότητα του συστατικού που είναι ήδη διαθέσιμη στην κουζίνα,
• ~S_M, 1 \le S_M < 100~, το μέγεθος της μικρότερης συσκευασίας στο κατάστημα,
• ~P_M, 10 \le P_M < 100~, η τιμή της μικρότερης συσκευασίας,
• ~S_V, S_M < S_V \le 100~, το μέγεθος της μεγαλύτερης συσκευασίας, και
• ~P_V, P_M < P_V \le 100~, η τιμή της μεγαλύτερης συσκευασίας.

Έξοδος

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

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

input

2 100
10 8 10 10 13 11
12 20 6 10 17 24

output

5

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

Στο πρώτο παράδειγμα, για ~99~ δολάρια η Liza θα αγοράσει τρεις μικρότερες και μία μεγαλύτερη συσκευασία από το πρώτο συστατικό, καθώς και μία μικρότερη και δύο μεγαλύτερες συσκευασίες του δεύτερου συστατικού ~(3\cdot 10 + 1\cdot 11 + 1\cdot 10 + 2\cdot 24 = 99)~.

Στη συνέχεια, ο σεφ θα έχει ~51~ μονάδες ~(8 + 3 \cdot 10 + 1\cdot 13)~ από το πρώτο συστατικό και ~60~ μονάδες ~(20 + 1\cdot 6 + 2\cdot 17)~ από το δεύτερο συστατικό, αρκετά για ~5~ μερίδες.

input

3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16

output

2