Air Bovinia łączy $N$ farm krów ($1 \le N \le 200$). Wybiera $K$ jako węzły przesiadkowe ($1 \le K \le 100,$ $K \le N$). Farmy mają numery $1..N$, węzły $1..K$.

Istnieje $M$ lotów w jedną stronę ($1 \le M \le 10,000$). Lot $i$ prowadzi z $u_i$ do $v_i$ i kosztuje $d_i$ dolarów ($1 \le d_i \le 1,000,000$).

Otrzymała $Q$ próśb o podróże w jedną stronę ($1 \le Q \le 10,000$), $i$-ta z $a_i$ do $b_i$. Z $a_i$ do $b_i$ wolno użyć dowolnego ciągu bezpośrednich lotów, nawet odwiedzając farmy wielokrotnie, ale trzeba uwzględnić co najmniej jeden węzeł, który może być początkiem, końcem lub pośrednią farmą. Z $a_i$ do $b_i$ może więc nie być poprawnej trasy. Dla pozostałych próśb znajdź jej minimalny koszt.

Wejście

• Wiersz $1$: całkowite $N$, $M$, $K$, $Q$.

• Wiersze $2..1+M$: wiersz $i+1$ zawiera $u_i$, $v_i$, $d_i$ dla lotu $i$.

• Wiersze $2+M..1+M+Q$: wiersz $1+M+i$ opisuje podróż $i$ przez $a_i$ i $b_i$.

Wyjście

• Wiersz $1$: liczba próśb spośród $Q$ mających poprawną trasę.

• Wiersz $2$: suma minimalnych kosztów wszystkich próśb mających poprawną trasę.

Przykład

Wejście 1

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

Wyjście 1

2
24

Uwagi

Są $3$ farmy o numerach $1\ldots3$, węzeł to $1$. Lot z $3$ do $1$ kosztuje $10$ itd. Prośby: $3\to2$, $2\to3$, $1\to2$.

$3\to2$ ma tylko trasę kosztu $10+7$. $2\to3$ nie ma trasy, bo z $2$ nic nie odlatuje. $1\to2$ ma tylko poprawną trasę kosztu $7$.

Autor zadania: Kalki Seksaria