Marisa có ~n~ tấm gỗ và sẽ sửa lại chúng để sử dụng, tấm gỗ thứ ~i~ sẽ có độ đẹp là ~A_i~ hoặc ~B_i~ (tuỳ vào mục đích sử dụng mà Marisa sẽ sửa chúng khác nhau).

Marisa dự định chọn ra ~k~ tấm gỗ để làm hàng rào bao quanh nhà. Trong đó, cô sẽ chọn ra ~k-1~ tấm để dựng hàng rào và ~1~ tấm để làm cửa. Khi đó, những tấm để làm hàng rào sẽ có độ đẹp là ~A_i~ và tấm để làm cửa sẽ có độ đẹp là ~B_i~.

Marisa đang cân nhắc số lượng tấm gỗ sử dụng để làm hàng rào, nên cô sẽ hỏi bạn ~q~ câu hỏi, mỗi câu hỏi là một số nguyên ~k~, hãy giúp cô tính độ đẹp lớn nhất có thể khi sử dụng ~k~ tấm gỗ.

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

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.
• Dòng thứ ba gồm ~n~ số nguyên ~B_i~.
• Dòng thứ tư gồm ~q~ số nguyên ~k~ theo thứ tự, mô tả các truy vấn.

Kết quả ghi ra tệp văn bản: xayhangrao.out

• In ra ~q~ số nguyên, số nguyên thứ ~i~ là đáp án truy vấn thứ ~i~.

Ví dụ

Input 1:

3 1
3 5 4
5 8 5
3

Output 1:

15

Input 2:

3 2
3 5 4
5 8 5
3 2

Output 1:

15 12

Giới hạn: Trong mọi test: ~1 \le n,q \le 10^5, 1 \le A_i, B_i \le 10^9~.

• Subtask 1 (25% số điểm): Marisa chỉ hỏi bạn một câu hỏi duy nhất với ~k = n~.
• Subtask 2 (25% số điểm): ~1 \le n,q \le 10~.
• Subtask 3 (25% số điểm): ~1 \le n,q \le 1000~.
• Subtask 4 (25% số điểm): Không có giới hạn gì thêm.

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

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

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Cho ~N~ đoạn gỗ, để xử lí chúng, ta cần:

• Thời gian xử lí đoạn gỗ đầu tiên là 1 phút.
• Sau khi xử lí xong đoạn gỗ có chiều dài ~l~ và trọng lượng ~w~, không mất thời gian xử lí nếu đoạn gỗ tiếp theo có chiều dài ~l'~ và trọng lượng ~w'~ thỏa mãn ~l \le l'~ và ~w \le w'~, ngược lại mất 1 phút để xử lí.

Tìm thời gian chuẩn bị ít nhất cho ~N~ đoạn gỗ.

Ví dụ có 5 đoạn: ~(9,4), (2,5), (1,2), (5,3), (4,1)~ thì thời gian ít nhất là 2 vì có thể xử lí theo thứ tự sau: ~(4,1), (5,3), (9,4), (1,2), (2,5)~.

Input

Dòng đầu là số lượng test ~T \le 100~, mỗi test gồm:

• Dòng đầu là số nguyên dương ~N \le 5000~.
• Sau đó ~N~ dòng tiếp theo gồm ~N~ cặp số nguyên dương ~(l_1,w_1), (l_2,w_2), ..., (l_N,w_N)~, ~l_i,w_i <= 10000~ là độ dài và trọng lượng khối gỗ.

Output

In ra T dòng, mỗi dòng là đáp án của test tương ứng.

Sample Test

Input:

3

5 
4 9 
5 2 
2 1 
3 5 
1 4

3 
2 2 
1 1 
2 2

3 
1 3 
2 2 
3 1

Output:

2
1
3

Một lớp học nhảy có ~n~ học viên nam và ~n~ học viên nữ. Cho ~m~ thông tin về các cặp học viên, thông tin thứ ~k~ ~(1 \le k \le m)~ cho biết học viên nam thứ ~i_k~ ~(1 \le i_k \le n)~ có thể nhảy cặp với học viên nữ thứ ~j_k~ ~(1 \le j_k \le n)~ .

Trong một buổi học, sau khi hướng dẫn cho tất cả các học viên, thầy giáo muốn chọn ra hai đôi nhảy, mỗi đôi gồm hai học viên (một nam và một nữ) để trình diễn và rút kinh nghiệm. Trong quá trình biểu diễn, hai cặp này sẽ đổi bạn nhảy cho nhau, do đó, thầy giáo muốn lựa chọn ra hai đôi nhảy mà khi đổi bạn nhảy, hai học viên ở đôi nhảy mới vẫn có thể nhảy cặp với nhau.

Yêu cầu: Cho ~m~ thông tin về các cặp học viên, hãy đếm số cách chọn hai cặp nhảy thỏa mãn. Hai cặp nhảy được gọi khác nhau nếu tồn tại một người thuộc vào hai cặp nhảy này nhưng không thuộc hai cặp nhảy kia.

Input

• Dòng đầu chứa hai số nguyên dương ~ n,m~ ~(m \le n^2)~
• Dòng thứ ~k~ ~(1 \le k \le m)~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~i_k, j_k~ ~(1 \le i_k , j_k \le n)~ mô tả thông tin về cặp học viên thứ ~k~.

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là số cách chọn hai cặp nhảy thỏa mãn.

Subtask

• ~20\%~ số test: ~n \le 50~
• ~20\%~ số test khác : ~n \leq 300~.
• ~20\%~ số test khác : ~n \leq 10^3, m \le 2 \times 10^4~.
• ~20\%~ số test khác : ~n \leq 5 \times 10^3, m \le 2 \times 10^4~.
• ~20\%~ số test còn lại : ~n,m \leq 10^5~.

Example

Input 1

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

Output 1

2

Explanation

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9

Mùa đông đang đến (hoặc có thể sẽ đi? Ai có thể chắc chắn được những ngày này đây) và một vị vua mới trỗi dậy ở phương Bắc. Thông điệp được truyền đi nhanh chóng trong những ngày này... Đó là lý do tại sao bạn, vị vua đang nổi lên, không còn nhiều thời gian nữa. Bạn cần tập hợp các chư hầu của mình. Tuy nhiên, nảy sinh ra một vấn đề. Bạn có thể chiếm đóng một vương quốc rộng lớn đến mức nào và bạn nên cử đi bao nhiêu người? Các quân sư của bạn đã xem xét kỹ những mảnh đất tiềm năng và đã xác định có bao nhiêu chư hầu của bạn sẽ được triệu tập để bảo vệ vương quốc mới của bạn. Vì bạn là một vị vua anh minh, bạn muốn giảm thiểu tối đa số lượng quân lính phải phục vụ trong quân đội của mình và thông báo điều đó tới hội đồng quân sư.

May mắn thay, kẻ thù của bạn vẫn còn khá yếu kém. Bạn chỉ cần phải đối mặt với một đội quân chỉ biết đi ngang và đi dọc (đối phương sẽ không thể đi chéo). Vương quốc của bạn được tính là được bảo vệ nếu không có một cách nào để tiến đánh vào kinh đô, dù xuất phát từ bất kì nơi đâu ở ngoài bản đồ và không vượt qua các vùng được bảo vệ. Các ô vuông ở trên bản đồ được đánh số là ~0~ nếu đó là núi, sẽ không ai có thể vượt qua được đó nên bạn không cần cử người bảo vệ. Và, do bạn không chắc chắn về những gì ẩn nấp sau đường biên giới (hoặc trong trường hợp này là đường viền của bản đồ), bạn phải giả định điều tồi tệ nhất và lên kế hoạch để bảo vệ kinh đô của mình.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~ miêu tả số hàng và số cột của bản đồ.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bản đồ. Ô trên dòng thứ ~i~ và cột ~j~ có giá trị là ~a_{i,j}~, có nghĩa là số người cần thiết để bảo vệ ô ~(i,j)~. Nếu ~a_{i,j} = 0~ nghĩa là đây là núi và bạn không cần cử ai để bảo vệ nó.
• Dòng cuối cùng gồm ~2~ số nguyên ~r,c~ miêu tả vị trí kinh đô của bạn.

Output

• In ra số quân ít nhất bạn cần huy động để có thể bảo vệ kinh đô.

Constraints

• ~1 \le n,m \le 300~
• ~1 \le a_{i,j} \le 10^5~.
• ~0 \le r \le n-1, 0 \le c \le m - 1~.

Sample Input 1:

7 8
42 42  0  0  0  0  0 16
77 11 14 42 42 42 10 16
88  0 42 47 42 65  0 16
42  0 44 42 39 42  0 94
76  0 38 42 42 87  0 42
77 11 42 42 42  5  5 42
42 42 0 0 0 42 76 88
3 4

Sample Output 1:

37

Explanation 1:

Dấu ~x~ là những ô cử quân tới để bảo vệ, những ô đen là những dãy núi và kí hiệu tòa thành chính là kinh đô.

Kết quả sẽ là ~37~.