Tại Earth-2729, có ~n~ quốc gia, quốc gia thứ ~i~ có sức mạnh quân sự ~c_i~. Hiện tại, đang có ~m~ cuộc xung đột quân sự diễn ra trên toàn cầu, cuộc xung đột thứ ~i~ giữa hai quốc gia ~u_i~ và ~v_i~.

Nhóm Azenzers muốn có những động thái để tránh tình hình chiến sự leo thang, tuy nhiên đây không phải là truyện tranh Marvel, họ không hề có siêu năng lực nào cả. Vậy nên nhóm muốn thành lập một liên minh gồm một số quốc gia để hợp tác quân sự, sao cho tổng sức mạnh quân sự của các nước này là lớn nhất và không có cuộc xung đột nào đang diễn ra giữa các quốc gia được lựa chọn để hợp tác.

Hãy giúp nhóm Azenzers tìm được liên minh quân sự tốt nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ .

• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_i~ là sức mạnh quân sự của từng quốc gia .

• Trong ~m~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ miêu tả xung đột thứ ~i~.

Output

• Gồm một số nguyên dương miêu tả tổng sức mạnh quân sự lớn nhất của liên minh thỏa mãn.

Constraints

• ~1 \le n \le 40, 0 \le m \le \frac{n \times (n-1)}{2}~
• ~1 \le c_i \le 10^9~
• ~1 \le u_i,v_i \le n; u_i \neq v_i~

Subtask

• Subtask ~1~ (~20~ điểm): ~n \le 20~
• Subtask ~2~ (~30~ điểm): ~n \le 30~
• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4 2
4 9 2 1
1 4
2 4

Sample Output 1

15

Explannation 1

• Chọn quốc gia ~1~, ~2~ và ~3~.

Hôm nay 3 nàng tiên ánh sáng đi tìm kho báu. Khi đến trước cửa hang động, họ nhìn thấy ~n~ cây nấm với màu sắc và kích cỡ khác nhau. Theo như truyền thuyết muốn mở cánh cửa hang động thì cần sắp xếp các cây nấm này theo thứ tự tăng dần của kích cỡ, chỉ được đổi chỗ 2 cây nấm ở cạnh nhau. Mỗi lần đổi chỗ 2 cây nấm cho nhau sẽ tốn 1 ma lực, nhưng nếu 2 cây nấm cùng màu thì không tốn chút sức nào cả.

Hãy giúp Sunny Milk và đồng bọn tính số ma lực tối thiểu để có thể mở cánh cửa hang động nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le c_i \le n~ là màu của cây nấm thứ ~i~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le s_i \le n~ là kích cỡ của cây nấm thứ ~i~.

Output

• In ra một số nguyên duy nhất là lượng ma lực tối thiểu cần để mở cánh cửa.

Sample Test

Input:

5
1 5 2 2 1
3 2 1 2 1

Output:

6

Cho lưới ô vuông ~n*n~. Các hàng đánh số từ ~1 ... n~ từ trên xuống dưới, các cột đánh số ~1...n~ từ trái sang phải. Ô ở hàng ~i~, cột ~j~ chứa số nguyên ~a_{ij}~ ~(1 \le a_{ij} \le 200)~.

Hãy đếm số hình chữ nhật của lưới có phần tử nhỏ nhất đúng bằng ~100~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. (~1 \le n \le 1000~).

• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên miêu tả lưới ô vuông.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~40\%~ số test có ~n \le 200~.
• ~40\%~ số test có ~n \le 500~.
• ~20\%~ số test có ~n \le 1000~.

Sample Input 1:

3
57 120 87
200 100 150
2 141 135

Sample Output 1:

8

Cho một cây gồm ~N~ đỉnh. Cạnh thứ ~i~ trên cây có trọng số ~w_i~. Độ dài đường đi giữa hai đỉnh ~u~ và ~v~ được định nghĩa là tổng các cạnh nằm trên đường đi phải qua ít cạnh nhất từ ~u~ tới ~v~. Chọn ~K~ đỉnh lá sao cho tổng độ dài đường đi giữa mọi cặp đỉnh trong ~K~ đỉnh đã chọn là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(1≤K≤N)~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa thông tin về một cạnh của cây từ nút ~u_i~ đến ~v_i~ với trọng số ~w_i~ ~(1≤w_i≤10^5)~.

Output

• Gồm một số nguyên duy nhất là tổng khoảng cách nhỏ nhất trong cách chọn K nút lá tốt nhất.

Scoring

• Sub1: ~1 ≤ N ≤ 20~;
• Sub2: ~1 ≤ N ≤10^5, K=2~;
• Sub3: ~1 ≤ N ≤2000, K=3~;
• Sub4: ~1 ≤ N ≤10^5, K≤100~.

Example

Input

4 2
1 2 2
1 3 3
1 4 4

Output

5

Input

4 3
1 2 2
1 3 3
1 4 4

Output

18

Cho hai dãy số nguyên ~a_1,a_2,...,a_n~ và ~b_1,b_2,...,b_n~. Bạn cần sử dụng thao tác sau đúng một lần:

• Chọn hai chỉ số ~[L,R]~ thỏa mãn ~1 \le L \le R \le n~ và hoán đổi vị trí hai dãy con ~a_L,a_{L+1},...,a_R~ với ~b_L,b_{L+1},...,b_R~.

Hãy đếm số cách thực hiện thao tác trên sao cho sau khi thực hiện, ít nhất một trong hai dãy ~a~ hoặc ~b~ trở thành hoán vị của các số từ ~1~ đến ~n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy ~b~.

Constraints

• ~2 \le n \le 2*10^5~

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~2~ (~40\%~ số điểm): ~n \le 5000~
• Subtask ~3~ (~30\%~ số điểm): Không ràng buộc gì thêm.

Output

• In ra số cách thực hiện thao tác trên.

Sample Input 1

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

Sample Output 1

8

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có ~n~ bến xe buýt được đánh số từ ~1~ tới ~n~ và có ~m~ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải ~A~ hoặc ~B~. Cụ thể, tuyến thứ ~i~ ~(1 \le i \le m)~ di chuyển giữa hai bến ui và vi với giá vé do công ty quản lý quy định là ~w_i~.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt. Hai công ty ~A~ và ~B~ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty ~A~ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty ~A~ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty ~B~ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty ~B~ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt ~s~ và nơi làm của Alice ở gần bến xe buýt ~t~ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~.

Input:

• Dòng đầu tiên chứa bốn số nguyên dương ~n, m, s~ và ~t~ ~(n, m \le 50000; s, t \le n; s \neq t)~;
• Dòng thứ ~i (1 \le i \le m)~ trong ~m~ dòng tiếp theo chứa bốn số nguyên dương ~c_i, u_i, v_i, w_i~ ~(u_i, v_i \le n; u_i \neq v_i; w_i \le 10^9)~ mô tả tuyến xe buýt thứ i trong đó ~c_i = 1~ nếu tuyến này được điều hành bởi công ty ~A~ hoặc ~c_i = 2~ nếu tuyến này được điều hành bởi công ty ~B~.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt ~s~ và ~t~ thông qua ~m~ tuyến xe.

Output:

• In ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~ cho Alice.

Subtask

• Subtask ~1~ ~(30\%)~: tất cả xe buýt đều được điều hành bởi công ty ~A~.
• Subtask ~2~ ~(30\%)~: ~n,m \le 5000~
• Subtask ~3~ ~(40\%)~: không ràng buộc gì thêm.

Sample Input 1

6 7 1 4
1 1 2 4
2 2 3 7
1 3 4 6
2 1 6 5
1 6 5 5
2 5 4 8
2 2 5 2

Sample Output 1

12

Explanation 1

Để đi từ ~1~ tới ~4~, Alice đi tuyến ~(1,2)~ của công ty ~A~ và hai tuyến ~(2,5)~ và ~(5,4)~ của công ty ~B~. Khi đó Alice cần trả cho công ty ~A~ ~4~ và công ty ~B~ ~8~ đơn vị tiền.