Where's That Fuel?

Το ηρωική ομάδα Star Fox βρίσκεται σε αποστολή να συλλέξει όσο το δυνατόν περισσότερα καύσιμα από διάφορους πλανήτες σε όλο το σύστημα Lylat. Υπάρχουν ~N~ (~1 \le N \le 10^5~) πλανήτες, και ο ~i~-οστος περιέχει ~A_i~ κυψέλες καυσίμων - αλλά ταξιδεύοντας εκεί από οποιονδήποτε άλλο πλανήτη χρησιμοποιεί ~B_i~ κυψέλες καυσίμου (~1 \le A_i, B_i \le 10^4~). Δυστυχώς, οι κυψέλες καυσίμου δεν είναι βιώσιμοι πόροι, οπότε αν επισκεφθεί ένα πλανήτη για δεύτερη φορά, δεν θα υπάρχει νέο καύσιμο για συλλογή.

Η ομάδα Star Fox ξεκινά στον πλανήτη ~P~ (~1 \le P \le N~)- ως εκ τούτου, μπορούν να συλλέξουν τις κυψέλες καυσίμου του άμεσα. Μπορούν στη συνέχεια να ταξιδεύουν σε όσους διαφορετικούς πλανήτες θέλουν, με οποιαδήποτε σειρά, όσο έχουν επαρκή καύσιμα για να καταναλώσουν σε κάθε πτήση (δηλαδή, ο αριθμός των κυψελών καυσίμου παραμένει μη αρνητικός). Τέλος, μπορούν να επιλέξουν να σταματήσουν σε οποιοδήποτε σημείο (ενδεχομένως ακόμη και πριν εγκαταλείψουν τον πλανήτη ~P~), με στόχο τη μεγιστοποίηση του αριθμού των κυττάρων καυσίμου με τα οποία καταλήγουν. Εάν αυτό μπορεί να γίνει με πολλούς τρόπους, Θα ήθελαν να μεγιστοποιήσουν τον αριθμό των διαφορετικών πλανητών που επισκέπτονται ως δευτερεύον στόχο. Μπορείτε να βοηθήσετε τους ήρωές μας;

Είσοδος

Η πρώτη γραμμή περιέχει δύο ακέραιους: ~N~ (~1 \le N \le 10^5~), ακολουθούμενη από ένα κενό, ακολουθούμενη από το ~P~ (~1 \le P \le N~), το οποίο αντιπροσωπεύει τον αριθμό των πλανητών, που ακολουθείται από τον αριθμό του πλανήτη εκκίνησης. Οι επόμενες ~N~ γραμμές περιέχουν το ~A_i~, ακολουθούμενο από ένα κενό, ακολουθούμενο από ~B_i~ (~1 \le A_i, B_i \le 10^4~).

Βαθμολογία

Μπορείτε να υποθέσετε ότι για περιπτώσεις δοκιμής αξίας 20% των βαθμών, ~N \le 10~.

Έξοδος

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

Παράδειγμα

input

5 2
12 12
10 100
8 3
4 5
25 15

output

25
4

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

Η ομάδα Star Fox ξεκινά στον πλανήτη ~2~, στον οποίο συλλέγουν ~10~ κυψέλες καυσίμου για αρχή. Θα πρέπει να συνεχίσουν ταξιδεύοντας στον πλανήτη ~3~, που θα τους κοστίσει ~3~ κυψέλες καυσίμου αλλά μετά θα αυξήσει τον αριθμό κυψελών καυσίμων που έχουν σε ~15~. Μετά, μπορούν να πετάξουν στον πλανήτη ~1~, ρίχνοντας τον αριθμό κυψελών καυσίμου τους στο ~3~ αλλά επαναφέροντάς τον γρήγορα στο ~15~. Τέλος, έχουν ακριβώς αρκετά καύσιμα να φτάσουν στον πλανήτη ~5~, όπου μπορούν να συλλέξουν τις κυψέλες καυσίμου του και να καταλήξουν με ~25~. Έπειτα θα πρέπει να σταματήσουν χωρίς νσ έχουν επισκεφθεί ποτέ τον πλανήτη ~4~.