Phone Plans

Ο δήμαρχος της CCO-χώρας, ο Jason, θέλει να εγκαταστήσει τηλεφωνικές γραμμές ανάμεσα σε ~N~ νοικοκυριά, τα οποία είναι αριθμημένα από το ~1~ έως το ~N~. Για να το καταφέρει αυτό, έχει ζητήσει από δύο αντίπαλες εταιρίες, την "Keenan Mobile Phones" και την "Chris Home Telephone", για τα τηλεφωνικά τους πλάνα. Ένα τηλεφωνικό πλάνο για μια εταιρία ανταποκρίνεται σε ένα συγκεκριμένο επίπεδο και κάθε τηλεφωνική γραμμή έχει ένα επίπεδο και μια εταιρία που σχετίζεται με αυτή. Αν έχετε αγοράσει ένα τηλεφωνικό πλάνο από μια εταιρία με επίπεδο ~l~, τότε μπορείτε να χρησιμοποιήσετε όλες τις τηλεφωνικές γραμμές των οποίων το επίπεδο είναι μικρότερο ή ίσο του ~l~ και σχετίζεται με την συγκεκριμένη εταιρία. Ένα τηλεφωνικό πλάνο επιπέδου ~l~ κοστίζει ~$l~ και δεν μπορείτε να διαλέξετε ένα τηλεφωνικό πλάνο που κοστίζει λιγότερο από ~$0~.

Ο μόνος τρόπος για δύο νοικοκυριά να επικοινωνήσουν το ένα με το άλλο είναι αν συνδέονται από μια διαδρομή τηλεφωνικών γραμμών της ίδιας εταιρίας. Ο Jason θα ήθελε να αγοράσει ένα τηλεφωνικό πλάνο από κάθε εταιρία ελάχιστου κόστους ώστε να υπάρχουν τουλάχιστον ~K~ διαφορετικά ζεύγη νοικοκυριών που μπορούν να επικοινωνήσουν μεταξύ τους.

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις χωρισμένους με κενό ακέραιους αριθμούς ~N, A, B~ και ~K~, οι οποίοι αντιπρωσοπεύουν τον αριθμό των νοικοκυριών, τον αριθμό των τηλεφωνικών γραμμών από την Keenan Mobile Phones, τον αριθμό των τηλεφωνικών γραμμών από την Chris Home Telephone και τον ελάχιστο αριθμό από τα ζεύγη νοικοκυριών που πρέπει να επικοινωνούν μεταξύ τους αντίστοιχα.

Οι επόμενες ~A~ γραμμές περιέχουν η καθεμία τρεις χωρισμένους με κενό ακέραιους αριθμούς ~u, v~ και ~l~, οι οποίοι αντιπροσωπεύουν μια τηλεφωνική γραμμή της εταιρίας Keenan Mobile Phones μεταξύ των νοικοκυριών ~u~ και ~v~ ~(1 \le u,v \le N)~ που έχουν επίπεδο ~l~ ~(1 \le l \le 10^9)~.

Οι επόμενες ~B~ γραμμές έχουν την ίδια μορφή με τις προηγούμενες ~A~ γραμμές αλλά για την εταιρία Chris Home Telephone.

Βαθμολογία

Βαθμοί	Περιορισμοί στο ~N~	Περιορισμοί στο ~A~ και ~B~	Περιορισμοί στο ~K~	Επιπλέον περιορισμοί
6	~1 \le N \le 2\,000~	~0 \le A,B \le 200\,000~	~0 \le K \le \frac {N(N-1)} {2}~	Κανένας
5	~1 \le N \le 200\,000~	~0 \le A,B \le 200\,000~	~0 \le K \le \frac {N(N-1)} {2}~	Η Keenan Mobile Phones συνδέεται μόνο σε νοικοκυριά με περιττό αριθμό και η Chris Home Telephone σε νοικοκυριά με άρτιο αριθμό
6	~1 \le N \le 200\,000~	~0 \le A \le 10~ ~0 \le B \le 200\,000~	~0 \le K \le \frac {N(N-1)} {2}~	Κανένας
8	~1 \le N \le 200\,000~	~0 \le A,B \le 200\,000~	~0 \le K \le \frac {N(N-1)} {2}~	Κανένας

Έξοδος

Εκτυπώστε το μικρότερο κόστος που χρειάζεται για να συνδεθούν τουλάχιστον ~K~ διαφορετικά ζεύγη νοικοκυριών ή -1 αν δεν είναι δυνατό.

Παράδειγμα

input

6 4 4 9
1 2 1
2 3 2
1 4 3
3 4 4
5 6 40
1 5 30
2 6 20
3 6 10

output

33

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

Για κάθε εταιρία, σκεφτείτε τις παρακάτω εικόνες ως τον τρόπο που συνδέονται τα ~6~ νοικοκυριά με τηλεφωνικές γραμμές:

Εάν ο Jason αγοράσει το τηλεφωνικό πλάνο επιπέδου ~3~ από την Keenan Mobile Phones και το τηλεφωνικό πλάνο επιπέδου ~30~ σπό την Chris Home Telephone, τότε τα ζεύγη νοικοκυριών ~(1,2), (1,3), (1,4), (2,3), (2,4), (2,4)~ μπορούν να επικοινωνούν μέσω των γραμμών της Keenan Mobile Phones και τα ζεύγη ~(1,5), (2,6), (3,6), (2,3)~ μπορούν να επικοινωνούν μέσω των τηλεφωνικών γραμμών της Chris Home Telephone. Δεν υπάρχει πιο φθηνός τρόπος.