Convex Hull

Ταξιδεύετε με ένα πλοίο σε ένα αρχιπέλαγος. Το πλοίο έχει κυρτό κύτος πάχους ~K~ εκατοστών. Το αρχιπέλαγος έχει ~N~ νησιά, αριθμημένα από το ~1~ έως το ~N~. Υπάρχουν ~M~ θαλάσσιες διαδρομές ανάμεσά τους, όπου η ~i~-οστή διαδρομή περνάει απευθείας μεταξύ δύο διαφορετικών νησιών ~a_{i}~ και ~b_{i}~ ~(1 \le a_{i},\;b_{i} \le N)~, χρειάζεται ~t_{i}~ λεπτά για να ταξιδέψει κανείς προς μια ή την αντίθετη κατεύθυνση, και έχει βράχια που φθείρουν το κύτος του πλοίου κατά ~h_{i}~ εκατοστά. Μπορεί να υπάρxουν πολλαπλές διαδρομές μεταξύ ενός ζεύγους νησιών.

Θα θέλατε να ταξιδέψετε από το νησί ~A~ σε ένα διαφορετικό νησί ~B\;(1 \le A,\;B \le N)~ κατά μήκος μιας ακολουθίας θαλάσσιων διαδρομών, τέτοιες ώστε το κύτος του πλοίου σας να παραμείνει άθικτο - με άλλα λόγια, τέτοιες ώστε το άθροισμα των τιμών ~h_{i}~ των διαδρομών να είναι αυστηρά μικρότερο από ~K~.

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τρεις ακέραιους αριθμούς ~K~, ~N~ και ~M\;(1 \le K \le 200,\;2 \le N \le 2000,\;1 \le M \le 10000)~, χωρισμένους με κενά διαστήματα.

Οι επόμενες ~M~ γραμμές περιέχουν η καθεμία ~4~ ακέραιους αριθμούς ~a_{i}~ ~b_{i}~ ~t_{i}~ και ~h_{i}~ ~(1 \le a_{i},b_{i} \le N,\;1 \le t_{i} \le 10^{5},\;0 \le h_{i} \le 200)~, χωρισμένους με κενά διαστήματα. Η ~i~-οστή γραμμή σε αυτό το σύνολο των ~M~ γραμμών περιγράφει την ~i~-οστή θαλάσσια διαδρομή (η οποία εκτείνεται από το νησί ~a_{i}~ στο νησί ~b_{i}~, διαρκεί ~t_{i}~ λεπτά και φθείρει το κύτος του πλοίου κατά ~h_{i}~ εκατοστά). Παρατηρήστε ότι ~a_{i} \neq b_{i}~ (δηλαδή η αφετηρία και το τέρμα μιας θαλάσσιας διαδρομής είναι διαφορετικά νησιά).

Η τελευταία γραμμή της εισόδου θα περιέχει δύο ακέραιους αριθμούς ~A~ και ~B~ ~(1 \le A,\;B \le N,\;A \neq B)~, τα νησιά μεταξύ μεταξύ των οποίων θέλουμε να ταξιδέψουμε.

Για το ~20%~ των βαθμών αυτού του προβλήματος, ~K = 1~ και ~N \le 200~. Για ακόμη ~20%~ των βαθμών αυτού του προβλήματος, ~K = 1~ και ~N \le 2000~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό : τον αριθμό που αντιπροσωπεύει τον ελάχιστο χρόνο που απαιτείται για να ταξιδέψετε από το ~A~ στο ~B~ χωρίς να φθαρεί το κύτος του πλοίου, ή ~-1~ για να δηλώσετε ότι δεν υπάρχει τρόπος να ταξιδέψει κανείς από το ~A~ στο ~B~ χωρίς να καταστρέψει το κύτος του πλοίου.

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

input

10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4

output

7

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

Η διαδρομή μήκους ~1~ από το ~1~ έως το ~4~ θα έφθειρε το κύτος του πλοίου. Οι τρεις διαδρομές μήκους ~2~ (~[1, 2, 4]~ και ~[1, 3, 4]~ με δύο διαφορετικούς τρόπους) διαρκούν τουλάχιστον ~8~ λεπτά. Η διαδρομή ~[1, 2, 3, 4]~ διαρκεί ~7~ λεπτά και φθείρει το κύτος του πλοίου μόνο κατά ~7~ εκατοστά, ενώ η διαδρομή ~[1, 3, 2, 4]~ διαρκεί ~13~ λεπτά και φθείρει το κύτος κατά ~5~ εκατοστά.

input

3 3 3
1 2 5 1
3 2 8 2
1 3 1 3
1 3

output

-1

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

Η απευθείας διαδρομή ~[1, 3]~ φθείρει το κύτος έως το ~0~, όπως και η διαδρομή ~[1, 2, 3]~.