Có ~N~ gói kẹo, gói thứ ~i~ chứa ~A_i~ viên kẹo. Hãy chia các gói thành ~2~ phần sao cho chênh lệch số viên kẹo giữa 2 phần là ít nhất.

Input

• Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 100~).
• Dòng tiếp theo chứa ~N~ số ~A_1, A_2, \ldots, A_N~ (~A_i \leq 50~).

Output

• In ra chênh lệch nhỏ nhất số viên kẹo giữa ~2~ nhóm kẹo.

Sample Test 1

Input:

5
2 4 9 3 5

Output:

1

Cho một dãy số ~A~ gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ và một số nguyên dương ~S~. Hãy tìm ~1~ dãy con có tổng ~S~ thuộc dãy ~A~.

Một dãy con tổng ~S~ thuộc dãy ~A~ có dạng là dãy ~A_{i_1}, A_{i_2}, A_{i_3}, \ldots, A_{i_{k - 1}}, A_{i_k}~ với

• ~1 \leq i_1 < i_2 < \ldots < i_k \leq N~;
• ~A_{i_1} + A_{i_2} + \ldots + A_{i_k} = S~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~S~ (~N, S \leq 10^3~)
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ (~A_i \leq 10^3~).

Output

• Nếu dãy con tổng ~S~ tổn tại, in ra các chỉ số trong ~A~ của phần tử thuộc dãy con đó. Nếu có nhiều dãy con thoả mãn thì in ra các chỉ số có thứ tự từ điển nhỏ nhất. Ngược lại, nếu không có dãy con thoả mãn thì in ra Does not exist.

Sample Test 1

Input:

5 7
1 3 5 9 3

Output:

1 2 5

Sample Test 2

Input:

4 17
1 3 5 7

Output:

Does not exist

Tỉnh A đang triển khai rất nhiều dự án xây dựng cơ sở hạ tầng cho Thành Phố. Tập đoàn xây dựng của hoangduong nhận được lời mời thầu ~n~ dự án (đánh số từ ~1~ đến ~n~). Sau khi tính toán thì tập đoàn này thấy để xây dựng dự án thứ ~i~ sẽ cần số vốn là ~c_i~ và sau khi hoàn thành sẽ thu hồi được vốn và thu được lợi nhuận là ~p_i~. Tập đoàn này có thể chọn thầu một số dự án bất kỳ trong danh sách trên và với những dự án được chọn, tập đoàn này phải bỏ toàn bộ vốn ra xây dựng và khi hoàn thành mới được thanh toán toàn bộ cả vốn lẫn lời.

Hiện tại, tập đoàn của hoangduong đang có số vốn là ~s~. Bạn hãy giúp cho tập đoàn này lựa chọn các dự án để nhận thầu sao cho có đủ vốn để xây dựng các dự án này và thu về lợi nhuận lớn nhất có thể nhé.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~s~ (~1 \le n \le 30~; ~1 \le s \le 300000~)
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, ..., c_n~ (~1 \le c_i \le 10000~)
• Dòng thứ ba chứa ~n~ số nguyên dương ~p_1, p_2, ..., p_n~ (~1 \le p_i \le 10000~)

Output

• Một số nguyên duy nhất là lợi nhuận lớn nhất có thể được.

Sample Test

Input

3 10 
4 5 7 
3 4 8

Output

8

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng ~N~ tờ tiền. Tờ tiền thứ ~i~ có mệnh giá ~a_i~. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

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

• Dòng đầu tiên chứa số nguyên dương ~N \ (N \le 500);~
• Dòng thứ hai bao gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá ~10^5~.

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

Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn ~N \le 3;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 12;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
1 2 4 5 2

Output

7

Giải thích:

• An có thể chọn những tờ tiền có mệnh giá ~1, 2, 4~.
• Bình chọn những tờ tiền còn lại có mệnh giá ~5, 2~.
• Mỗi người sẽ nhận được tổng số tiền là ~7~. Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

Input

5
9 8 4 5 13

Output

17

Giải thích:

• An sẽ chọn những tờ tiền có mệnh giá ~9, 8~.
• Bình sẽ chọn những tờ tiền có mệnh giá ~4, 13~.
• Mỗi người sẽ nhận được tổng số tiền là ~17~. Tờ tiền còn lại có mệnh giá ~5~ sẽ đem đi đầu tư.

Cho một dãy ngoặc ~s~ độ dài ~n~, sở dĩ gọi là dãy ngoặc bởi nó chỉ chứa hai loại kí tự là ( và ). Ta định nghĩa về dãy ngoặc đúng như sau:

• () là một dãy ngoặc đúng
• Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng

Dãy ngoặc ~s~ của chúng ta có thể không phải là dãy ngoặc đúng, nhưng nó không sai. Bởi nó có thể chứa nhiều dãy ngoặc đúng trong mình, thậm chí có thể chứa dãy ngoặc đúng đẹp.

Một dãy ngoặc đúng gọi là đẹp nếu quay dãy đó ~180~ độ, ta thu được chính nó. Ví dụ, ~()()~ hay ~(())~ là dãy ngoặc đúng đẹp; còn ~)()(~ và ~()(())~ thì không, bởi ~)()(~ không phải dãy ngoặc đúng, ~()(())~ thực hiện quay ~180~ độ thu được ~(())()~

Yêu cầu: Đếm số dãy ngoặc đẹp là dãy con (không cần liên tiếp) của ~s~. Hai dãy con được gọi là khác nhau nếu có một kí tự ~s_i~ của ~s~ xuất hiện trong dãy này mà không xuất hiện trong dãy kia. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 500~).
• Dòng thứ hai chứa chứa một xâu kí tự mô tả ~s~.

Output

• Một số nguyên duy nhất là số dãy ngoặc đúng đẹp của dãy con ~s~.

Subtasks

Example

Sample Input

6
)))())

Sample Output

2

Note

• Có hai dãy con ~(4, 5)~ và ~(4, 6)~.

Đấ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à ~1~.

Luật pháp của ~ABC~ rất lạ, có ~k~ bộ ba được coi là "xấu" ~(a_i,b_i,c_i)~, khi di chuyển, bạn không được đi liên tiếp qua các thành phố ~a_i,b_i,c_i~. Lưu ý rằng, vẫn có thể đi theo thứ tự liên tiếp ~a_i,c_i,b_i~.

Bạn cần đi từ thành phố ~1~ tới ~n~, hãy tìm cách di chuyển ngắn nhất.

Input

• Dòng đầu chứa ba số nguyên ~n,m,k~ ~(n \le 3000; 1 \le m \le 2 \times 10^4; 0 \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~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~k~ dòng sau, mỗi dòng gồm ba số nguyên dương ~a_i,b_i,c_i~ ~(1 ≤ a_i, b_i, c_i ≤ n) ~

Output

• Dòng đầu chứa một số ~d~ là đường đi ngắn nhất, nếu không có hãy in ra ~-1~.

Subtask

• Subtask ~2~: Không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

2

Cho một đồ thị có hướng không trọng số gồm ~n~ đỉnh và ~m~ cạnh. Bạn đang đứng ở đỉnh ~S~ của đồ thị và mục tiêu của bạn là đến được đỉnh ~T~. Tuy nhiên, khác với bình thường, mỗi bước đi của bạn chỉ có thể đi qua đúng ~3~ cạnh nối tiếp nhau bắt đầu từ đỉnh đang đứng. Ví dụ, có bốn cạnh ~(1,2), (2,3), (3,4), (3,5)~, khi đứng ở đỉnh ~1~ thì trong một bước bạn chỉ được đi tới đỉnh ~4~ hoặc ~5~.

Cho đỉnh ~S~ và ~T~ hãy tìm số bước đi ngắn nhất để từ đỉnh ~S~ tới được ~T~.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~n,m~, miêu tả số đỉnh và số cạnh.
• ~m~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả cạnh một chiều ~u,v~.
• Dòng cuối gồm ~2~ số nguyên dương ~S~ và ~T~ miêu tả đỉnh xuất phát và đỉnh đích.

Output

• In ra một số là số bước ít nhất để đi từ ~S~ tới ~T~, nếu không có cách đi nào thì in ra ~-1~.

Điều kiện

• ~1 \le n,m \le 2*10^5~

Ví dụ

Input 1:

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

Output 1:

2

Input 2:

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

Output 2:

-1

Vào một ngày đẹp trời, bỗng dưng Thinkies đi lạc vào một mê cung. Mê cung được biểu diễn dưới dạng một ma trận ~n*m.~ Ô hàng ~i~, cột ~j~ của mê cung được gọi là ô ~(i,j)~. Mê cung này rất đặc biệt, có ~p~ ô lối vào và ~q~ ô lối ra. Thinkies có thể xuất phát từ một ô bất kì trong ~p~ ô lối vào đó, và có thể thoát ra bằng cách đi tới một ô bất kì trong ~q~ ô lối ra. Mỗi ô đều chứa những giá trị riêng, ô ~(i,j)~ có giá trị ~a(i,j)~. Từ một ô ~(i,j)~ bất kì, Thinkies có thể di chuyển theo 2 cách (đều mất một đơn vị thời gian):

• Di chuyển sang ô kề cạnh với nó (từ ô ~(i,j)~ có thể tới ô ~(u,v)~ nếu ~(u,v)~ kề cạnh với ~(i,j)~ và ~a(u,v) \neq 0~).
• Sử dụng phép teleport, di chuyển sang ô ~(u,v)~ nếu ~u*v = a(i,j)~ và ~a(u,v) \neq 0~. Tuy nhiên, Thinkies chỉ có thể sử dụng được ~k~ lần phép teleport này mà thôi. Lưu ý, nếu trên các ô lối vào hoặc lối ra có giá trị a(u,v) = 0 thì ta sẽ không thể nào xuất phát hoặc đi vào ô đó. Hãy tìm cách đưa Thinkies ra khỏi mê cung sớm nhất có thể!

Input

• Dòng đầu gồm 3 số ~n,m,k (1 \le n, m \le 1000, k \le 3)~
• ~n~ dòng sau, mỗi dòng gồm m số ~a(i,j)~ biểu hiện mê cung
• Dòng tiếp theo gồm 2 số tự nhiên ~p,q (p+q \le n*m)~.
• ~p~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối vào.
• ~q~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối ra.

Output:

Số đơn vị thời gian ít nhất để Thinkies có thể ra khỏi mê cung, nếu không thể thoát ra in ra số ~-1~.

Ràng buộc

~a(i, j) \le 6 * 10 ^ 6~

• Subtask 1: ~n \le 50, m \le 50, k = 0~. (20%)
• Subtask 2: ~n \le 1000, m \le 1000, k = 0~. (30%)
• Subtask 3: ~n \le 50, m \le 50.~ (20%)
• Subtask 4: ~n,m \le 1000, k \le 3.~ (30%)

Sample Test 1

Input:

3 3 1
6 1 1
1 1 1
1 1 1
1 1
1 1
3 3

Output:

2

Sample Test 2

Input:

2 2 3
0 1 
2 1
1 1
1 1
2 1 

Output:

-1

Sample Test 3

Input:

2 2 3
2 1 
0 1
1 1
1 1
2 1 

Output

-1

Giải thích

• Ở test 2, do ô ~(1,1)~ có ~a(1,1) = 0~ nên ta không thể xuất phát từ ô đó, nên sẽ không thể đi ra.
• Ở test 3, do ô ~(2,1)~ có ~a(2,1) = 0~ nên ta không thể đi vào ô đó, nên không thể thoát ra mê cung.

Cho một đồ thị vô hướng gồm ~n~ đỉnh ~m~ cạnh. Cạnh ~i~ nối giữa đỉnh ~u_i~ và ~v_i~ và có kí tự ~c_i~ được viết lên trên nó.

Hãy tìm một đường đi từ ~1~ đến ~n~ ngắn nhất mà sau khi viết các kí tự có được khi đi qua các cạnh là một xâu palindrome. Nếu không tồn tại bất kì đường đi nào thỏa mãn là palindrome, in ra ~-1~.

Lưu ý: Đồ thị có thể tồn tại khuyên và cạnh lặp, các đỉnh và cạnh có thể đi qua lại nhiều lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~u_i, v_i, c_i~ mô tả cạnh thứ ~i~ của đồ thị.

Output

• Nếu tồn tại một đường đi tạo ra xâu palindrome, in ra độ dài ngắn nhất có thể. Nếu không, in ra ~-1~.

Sample Input 1

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 1

5

Explanation 1

Đi qua các cạnh ~2, 3, 4, 5, 5~, ta nhận được xâu aabaa.

Sample Input 2

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 2

-1

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Có ~n~ thành phố và ~m~ con đường hai chiều. Cần vận chuyển các mặt hàng thiết yếu từ thành phố ~1~ tới tất cả các thành phố khác (việc vận chuyển tới các thành phố khác luôn thực hiện được).

Nhưng mọi con đường đều có thu phí. May mắn thay, bạn có ~k~ thẻ ưu đãi, có nghĩa là khi đi từ thành phố ~1~ tới bất kì thành phố nào khác, bạn có thể chọn tối đa ~k~ con đường và không bị tính phí khi đi qua ~k~ con đường đó.

Bạn cần xác định chi phí tối thiểu để có thể chuyển hàng tới mỗi thành phố. Lưu ý bạn có thể xem việc vận chuyển hàng hóa từ thành phố ~1~ tới các thành phố khác là độc lập nhau.

Input

• Dòng đầu tiên chứa số nguyên ~n, m, k~ ~(1 \leq n \leq 10^{5}, 1 \leq m \leq 5 \times 10^{5}, 1 \leq k \leq 18)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u, v, w~ ~(1 \leq u, v \leq n, 1 \leq w \leq 10^{6})~ mô tả ~1~ con đường nối ~2~ thành phố ~u, v~ với chi phí ~w~ để đi qua.

Output

• Gồm ~n~ số nguyên, số thứ ~i~ ứng với chi phí tối thiểu với thành phố ~i~.

Example

Sample input

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

Sample output

0 0 0 2 2

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường một chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và có chi phí ~t_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~. Tuy nhiên anh ta chỉ mang đúng ~K~ đồng tiền.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất từ thành phố ~1~ tới ~n~ mà chỉ mất tổng chi phí ít hơn hoặc bằng ~K~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• Dòng thứ hai chứa số nguyên dương ~K~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,t_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và chi phí ~t_i~.

Output

• In ra độ dài đường đi ngắn nhất từ ~1~ tới ~n~ mà tổng chi phí không quá ~K~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~ và tiêu không quá ~K~, in ra ~-1~.

Constraints

• ~1 \le n \le 100~.
• ~1 \le m \le 1000~.
• ~1 \le k \le 10000~.
• ~1 \le l_i \le 1000~.
• ~0 \le t_i \le 1000~.

Subtasks

• Subtask ~1~: ~1 \le n,m \le 20~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

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

Sample Output 1:

11

Explanation 1:

Đi theo lộ trình ~(1,3,5,4,6)~.

Sample Input 2:

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

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~ tiêu không quá ~0~.