Đất nước ~ABC~ gồm ~n~ thành phố nối với nhau bởi ~m~ con đường. Con đường thứ ~i~ nối hai chiều giữa hai thành phố ~u_i~ và ~v_i~, với độ dài là ~x_i~. Thủ đô của ~ABC~ là thành phố ~1~, và có ~k~ chuyến tàu hai chiều, chuyến thứ ~i~ nối từ thủ đô tới thành phố ~s_i~ có độ dài là ~y_i~.

Để tránh gây lãng phí, chính phủ đang muốn xóa đi một số chuyến tàu. Hãy chỉ ra số chuyến tàu nhiều nhất có thể xóa sao cho độ dài của đường đi ngắn nhất từ mọi thành phố tới thủ đô đều không đổi.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 10^5; 1 \le m \le 3 \times 10^5; 1 \le k \le 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương ~u_i, v_i, x_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i; 1 \le x_i \le 10^9)~.
• ~k~ dòng sau, mỗi dòng gồm hai số nguyên dương ~s_i~ và ~y_i~. ~(1 \le s_i \le n; 1 \le y \le 10^9)~

Dữ liệu đảm bảo rằng luôn có cách đi từ một thành phố bất kì tới thủ đô, đồng thời có thể có cạnh lặp.

Output

• Gồm một dòng chứa một số là số chuyến tàu có thể bị xóa lớn nhất tìm được.

Sample Input 1

5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5

Sample Output 1

2

Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :

• Ban đầu chỉ có ~1~ ô bị cháy.
• Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.

Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:

• Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?

Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:

Input

• Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
• ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~

Output

• In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.

Sample Input

4 4 2
2 1
2 0

Sample Output

2 
34

Subtask

• ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
• ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
• ~60\%~ số test còn lại không có điều kiện gì thêm

Trong cơn sốt tiền điện tử, bạn vô tình Long x120 một meme coin và giờ đang thành tỉ phú. Bây giờ bạn đang đau đầu không biết phải ngủ ở đâu trong căn phòng rộng lớn của mình.

Phòng của bạn được miêu tả trên một trục ~OX~, có ~n~ chiếc đèn, chiếc thứ ~i~ có công năng là ~p_i~ và độ sáng là ~c_i~ (chú ý dãy ~p~ tăng dần). Độ sáng mà chiếc đèn thứ ~i~ chiếu vào một vị trí ~x~ trên trục ~OX~ được tính bằng công thức: ~f(i,x) = max(0,c_i - |x-p_i|)~.

Giả sử bạn định ngủ tại vị trí ~x~ (với ~x~ là một số nguyên) trên trục, thì chất lượng của ánh sáng ~S(x)~ sẽ là tổng của toàn bộ ~f(i,x)~, nói cách khác bằng ~\sum_{i=1}^{n} f(i,x)~.

Bạn sẽ chỉ có thể ngủ ngon nếu tổng này lớn hơn hoặc bằng ~k~, vậy nên hãy tìm tất cả các vị trí ~x~ sao cho ~S(x) \ge k~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ ~(1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18})~.

• Dòng thứ hai gồm ~n~ số nguyên ~p_1, p_2, \dots, p_n~ ~(|p_i| \leq 10^{12}, p_1 < p_2 < \dots < p_n)~.

• Dòng thứ ba gồm ~n~ số nguyên ~c_1, c_2, \dots, c_n~ ~(1 \leq c_i \leq 10^{12})~.

Output

• In ra số vị trí ~x~ giúp bạn ngủ ngon.

Subtask

• Subtask ~1~ ~(20\%)~: ~n \le 10, |p_i|, |c_i| \le 100~
• Subtask ~2~ ~(30\%)~:~|p_i|, |c_i| \le 2 \times 10^5~
• Subtask ~3~ ~(30\%)~: ~n \le 3000~
• Subtask ~4~ ~(20\%)~: Không giới hạn gì thêm.

Example

Input 1

4 6
-5 -3 0 7
3 2 6 1

Output 1

2

Explanation 1

Tổng độ sáng tại các vị trí nguyên trong khoảng ~[-7, 7]~ như sau:

~\{1,2,4,5,6,5,5,6,5,4,3,2,1,0,1\}~.

Chỉ tại các vị trí ~-3~ và ~0~, tổng độ sáng mới đạt ít nhất ~k~.

Tại tất cả các vị trí nguyên nằm ngoài khoảng ~[-7, 7]~ đều không thỏa mãn.

Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.