Vương quốc VNOI gồm ~n~ thành phố được liên kết với nhau bằng ~m~ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ ~i~ kết nối hai thành phố ~u_i,v_i~, và sẽ tốn ~w_i~ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới VNOI. Bạn xuất phát từ thành phố ~st~ và có dự định đi tới thành phố ~en~ bằng xe của mình. Tất nhiên đi xe thì phải tốn nhiên liệu, và xe của bạn có một bình xăng chứa được tối đa ~t~ lít xăng.

VNOI có ~s~ trạm xăng. Trạm xăng thứ ~i~ được phân bố ở thành phố ~p_i~ và có chi phí cho mỗi lít xăng là ~c_i~. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được ~t~ lít xăng thôi).

Bạn bắt đầu từ thành phố ~st~ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ ~st~ tới ~en~.

Input

• Dòng đầu gồm ~3~ số nguyên dương ~n,m,s~ ~(2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100)~
• Dòng tiếp theo gồm một số nguyên dương ~t~ ~(1 \le t \le 10^5)~ mô tả sức chứa của bình xăng.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n; 1 \le w_i \le t)~ miêu tả con đường thứ ~i~.
• ~s~ dòng tiếp theo, dòng thứ ~i~ gồm hai só nguyên dương ~p_i,c_i~ ~(1 \le p_i \le n; 1 \le c_i \le 100)~ miêu tả trạm xăng thứ ~i~.
• Dòng cuối cùng gồm hai số nguyên dương ~st,en~ ~(1 \le st, en \le n)~ miêu tả vị trí ban đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để di chuyển.

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 100; m \le 100; t \le 500~
• Subtask ~2~ ~(30\%)~: ~t \le 500~
• Subtask ~3~ ~(40\%)~: Không giới hạn gì thêm.

Sample Input 1

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1

5500

Sample Input 2

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2

1340

Sample Input 3

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3

61