Tóm tắt đề bài

Có ~n~ game, game thứ ~i~ có độ hấp dẫn ~k_i~.

Nam có ~t~ đơn vị thời gian để chơi game theo thứ tự từ ~1~ đến ~n~.

Mỗi game khi đến lượt Nam, cậu có thể:

Xem + chơi hết game → tốn ~a~ đơn vị thời gian và nhận toàn bộ độ hấp dẫn ~k_i~.

Chỉ xem mà không chơi → tốn ~b~ đơn vị thời gian và nhận 0 độ hấp dẫn.

Chỉ khi đã chơi hết hoặc bỏ qua mới chuyển sang game tiếp theo.

Mục tiêu: Tính tổng độ hấp dẫn tối đa có thể đạt sau t đơn vị thời gian.

Input

Dòng đâu tiên chứa ~4~ số nguyên dương ~n, t, a, b~ (~n \le 2*10^5; t \le 10^9, b < a \le 10^9~)

Dòng thứ hai chứa ~n~ số nguyên dương ~k_i~ (~k_i \le 10^9~)

Output

Một số nguyên: độ hấp dẫn tối đa có thể đạt.

Test mẫu

3 5 2 1
2 2 4

6

Scoring

Subtask 1 (20%): ~k_i \ge k_{i+1}~ với ~i = 1,..., n-1~

Subtask 2 (40%): ~n, t \le 1000~

Subtask 3 (40%): ~k_i < k_{i+1}~ với ~i = 1,..., n-1~

Có ~N~ địa điểm và ~M~ con đường một chiều.

Đường thứ i từ ~u_i~ đến ~v_i~ có thời gian đi bộ ~a_i~ và thời gian đi xe đạp ~b_i~ (luôn nhỏ hơn hoặc bằng a_i)

Quang và Vinh xuất phát từ địa điểm ~1~.

Vinh muốn đến địa điểm ~K~ không muộn hơn thời điểm ~X~.

Quang có thể:

Đạp xe từ đầu đến cuối (đi xe ở mọi chặng)

Hoặc tại một địa điểm duy nhất nào đó, Quang có thể chở Vinh đi xe đạp (dùng thời gian ~b_i~ thay cho ~a_i~) để giúp Vinh đến ~K~ kịp giờ ~X~.

Sau khi giúp Vinh xong, Quang tiếp tục đi xe đạp đến địa điểm ~N~ càng sớm càng tốt.

Yêu cầu: Tìm thời gian nhỏ nhất để Quang đến được địa điểm ~N~ mà vẫn giúp được Vinh đến ~K~ không muộn hơn ~X~. Nếu không thể giúp được Vinh đúng hạn, in ~-1~.

Input

Dòng 1: Chứa 4 số nguyên ~N, M, K, X~ (~K ≤ N ≤ 10^5, X ≤ 10^9~)

M dòng tiếp: ~u_i, v_i, a_i, b_i~ (~1 ≤ u_i, v_i ≤ N, 1 ≤ b_i ≤ a_i ≤ 10^4~)

Output

Một số nguyên: thời gian nhỏ nhất để Quang đến N và vẫn giúp Vinh đến ~K~ kịp giờ ~X~.

Nếu không có phương án hợp lệ, in ~-1~.

Test mẫy

Input

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

Output

3

Scoring

Subtask 1 (~30\%~): ~N, M \le 1000~

Subtask 2 (~40\%~): ~N, M \le 10^5, K = N~

Subtask 3(~30\%~): ~1000 < N, M \le 10^5~

Đất nước xinh đẹp ABC có ~n~ thành phố lớn, có ~n - 1~ con đường cao tốc quan trọng, giữa hai thành phố bất kì đều có thể đến được nhau bằng các con đường cao tốc này. Cho biết con đường thứ ~i~ nối thành phố ~x_i, y_i~ có tốc độ chạy xe hiện tại ~v_i~, chi phí để nâng cấp đường là ~c_i~, sau nâng cấp thi tốc độ đạt được ~s_i~.

Tốc độ lưu thông giới hạn giữa hai thành phố ~u, v~ được tính bằng tốc độ nhỏ nhất của đoạn trên đường nối chúng.

Nhằm phát triển kinh tế, người ta đã đưa ra ~Q~ giả định nâng cấp. Giả định thứ ~i~ cần sử dụng một khoản tiền ~m_i~ để nâng cấp đường đi từ thành phố ~a_i~ đến ~b_i~.

Yêu cầu: Với mỗi giả định nâng cấp, hãy tính tốc độ lưu thông giới hạn lớn nhất có thể đạt được.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~2 ≤ n ≤ 10^5~) là số thành phố;

Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo có ~5~ số nguyên ~x_i, y_i, v_i, c_i, s_i~ (~1 ≤ x_i, y_i ≤ n, 1 ≤ v_i < s_i ≤ 10^9, 1 ≤ c_i ≤ 10^9~), thể hiện thông tin hai thành phố ~x_i~ và ~y_i~ có đường nối trực tiếp, tốc độ chạy xe hiện tại là ~v_i~, chi phí nâng cấp đường là ~c_i~, tốc độ chạy xe sau nâng cấp là ~s_i~

Dòng tiếp theo chứa số nguyên ~Q~ (~1 ≤ Q ≤ 10^5~) là số giả định nâng cấp; Dòng thứ ~i~ trong Q dòng tiếp theo chứa ba số nguyên ~a_i, b_i, m_i~ (~1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ m_i ≤ 10^18~) mô tả giả định nâng cấp thứ ~i~.

Output

Gồm ~Q~ dòng, dòng thứ ~i~ ghi số nguyên là tốc độ lưu thông giới hạn lớn nhất trên đường đi giữa 2 thành phố ~a_i, b_i~ sau nâng cấp.

Test mẫu

Input

6
1 2 5 7 10
1 3 4 8 9
3 4 7 1 15
3 5 6 3 11
3 6 5 6 8
3
2 4 15
6 4 5
3 5 10

Output

7
5
11

Giải thích: Giải thích ví dụ: Mỗi đỉnh là một thành phố. Trên các cạnh viết thêm tốc độ lái xe hiện tại, chi phí nâng cấp và tốc độ sau khi nâng cấp.

Giả định 1: Nâng cấp đường (1, 2) được tốc độ 10, chi phí 7. Nâng cấp đường (1,3) được tốc độ 9, chi phí 8. Tổng chi phí là 15, nên không nâng cấp tiếp được đường (3,4). Đường đi giữa 2 và 4 có các tốc độ lần lượt là 10, 9, 7. Tốc lưu thông giới hạn lớn nhất đạt được là 7.

Giả định 2: Số tiền không đủ để tăng tốc độ tối thiểu trên đoạn (3,6) nên tốc độ lưu thông lưu thông giới hạn lớn nhất là 5.

Giả định 3: Nâng cấp (3,5) để có tốc độ lưu thông giới hạn lớn nhất là 11.

Scoring

Subtask 1 (~40\%~): ~2 ≤ n, q ≤ 1000~

Subtask 2 (~30\%~): Mỗi thành phố được nối không quá 2 thành phố khác;

Subtask 3 (~30\%~): Không có ràng buộc thêm.

```

Cho một bảng hình chữ nhật ~a~ gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô giao nhau giữa hàng ~i~ với cột ~j~ gọi là ô ~(i,j)~ có ghi một giá trị nguyên dương ~a_{i,j}~.

Yêu cầu: Hãy tìm một hình chữ nhật con của bảng ~a~ thỏa mãn các điều kiện sau:

• Các số ghi trong hình chữ nhật được chọn phải hoàn toàn phân biệt (không có số nào xuất hiện nhiều hơn một lần);

• Hình chữ nhật con được chọn phải có diện tích (số hàng × số cột) lớn nhất có thể.

Input

Dòng 1 chứa hai số nguyên dương ~m, n~ (~m, n ≤ 400~);

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên dương ~a_{i,1}, a_{i,2}, …, a_{i,n}~.

Các số đều có giá trị không vượt quá ~10^6~.

Output

Một số nguyên duy nhất là diện tích hình chữ nhật con được chọn.

Test mẫu

Input

3 3  
1 3 1  
4 5 6  
2 6 1  

Output

6

Giải thích: Hình chữ nhật có góc trái trên là ô (1,1) và góc phải dưới là ô (3,2).

Scoring

Subtask 1 (~25\%~): ~m, n ≤ 20; a_{i,j} ≤ 10^4~;

Subtask 2 (~25\%~): ~20 < m, n ≤ 100; a_{i,j} ≤ 10^4~;

Subtask 3 (~50\%~): ~100 < m, n ≤ 400~.

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ n; i = 1, 2, ..., n~). Một đoạn con tốt gồm các phần tử liên tiếp của dãy sao cho:

• Ít nhất 1 số xuất hiện đúng một lần;
• Ít nhất 1 số xuất hiện đúng hai lần;
• ...
• Ít nhất 1 số xuất hiện đúng ~k~ lần.

Hai đoạn con được gọi là khác nhau nếu tồn tại chỉ số đầu hoặc cuối của đoạn khác nhau.

Hãy đếm số đoạn con tốt của dãy đã cho.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n, k~ (~n ≤ 10^5; k ≤ 4~);

Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~1 ≤ a_i ≤ n~) là giá trị của các phần tử của dãy ~a~.

Output

Một số nguyên là số lượng đoạn con tốt thỏa mãn yêu cầu của đề bài.

Test mẫu

Input

3 1  
1 2 1  

Output

6

Giải thích: Có 6 đoạn con tốt thỏa mãn là: [1]; [2]; [1]; [1,2]; [2,1]; [1,2,1].

Input

6 3  
5 6 5 4 5 5  

Output

1  

Giải thích: Chỉ có 1 đoạn con tốt duy nhất gồm toàn bộ các số là: [6,5,6,4,5,5].

Input

6 2  
5 4 5 2 6 5  

Output

5  

Giải thích: Có 5 đoạn con tốt là: [5,4,5]; [5,4,5,2]; [5,4,5,2,6]; [4,5,2,6,5]; [5,2,6,5].

Scoring

Subtask 1 (~30\%~): ~n ≤ 1000~

Subtask 2 (~20\%~): ~1 ≤ a_i ≤ k, ∀i = 1, 2, ..., n~

Subtask 3 (~30\%~): ~k = 1~

Subtask 4 (~20\%~): Không có ràng buộc gì thêm.

Cho một đồ thị dạng cây có ~n~ đỉnh và ~n - 1~ cạnh, các đỉnh được đánh số từ ~1~ đến ~n~. Mỗi đỉnh ban đầu có màu đen hoặc trắng.

Một đường đi ~P~ được gọi là tốt nếu sau khi áp dụng quy trình đổi màu sau đây, ta thu được cây chỉ gồm các đỉnh trắng:

Dọc theo đường đi ~P~, mỗi lần đi qua một đỉnh ~u~ thì màu của ~u~ sẽ bị đổi (đen thành trắng, trắng thành đen).

Yêu cầu: Xác định số đỉnh ít nhất của một đường đi tốt. Chú ý rằng một đỉnh có thể được đi qua nhiều lần, và ban đầu luôn tồn tại ít nhất một đỉnh màu đen.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~2 ≤ n ≤ 5×10⁵~) — số đỉnh của cây.

Dòng thứ hai chứa một xâu gồm ~n~ ký tự '0' hoặc '1':

'0' nghĩa là đỉnh ban đầu có màu đen

'1' nghĩa là đỉnh ban đầu có màu trắng

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 ≤ u, v ≤ n~) mô tả một cạnh nối đỉnh ~u~ và ~v~.

Output

Một số nguyên là số đỉnh tối thiểu của một đường đi tốt.

Test mẫu

Input

3
010
1 2
2 3

Output

4

Giải thích: Một trong những đường đi tối ưu: 1 → 2 → 3 → 2

Xuất phát từ đỉnh 1, đổi màu 1 (đen → trắng)

Đến đỉnh 2, đổi màu 2 (trắng → đen)

Đến đỉnh 3, đổi màu 3 (đen → trắng)

Quay lại đỉnh 2, đổi màu 2 (đen → trắng) → Tất cả các đỉnh đều trắng.

Input

5
01100
1 2
1 5
2 3
2 4

Output

5

Giải thích: Một trong những đường đi tối ưu: 5 → 1 → 2 → 4 → 2

Scoring

Subtask 1 (~27\%~ số điểm): ~2 ≤ n ≤ 100~

Subtask 2 (~20\%~ số điểm): Mỗi đỉnh có bậc không quá 2

Subtask 3 (~28\%~ số điểm): Tất cả các đỉnh đều tô màu đen từ đầu

Subtask 4 (~25\%~ số điểm): Không có ràng buộc thêm