Alyona có con số yêu thích là ~k~ và vì cô còn nhỏ, ~k~ không vượt quá ~10~. Giờ đây, cô muốn chọn ~k~ ĐOẠN con không rỗng của chuỗi ~s~ sao cho các ĐOẠN này xuất hiện dưới dạng ĐOẠN con không giao nhau của chuỗi ~t~ và theo đúng thứ tự như trong chuỗi ~s~. Cô cũng quan tâm đến việc độ dài của chúng là lớn nhất có thể trong tất cả các biến thể.

Bạn cần tìm ~k~ ĐOẠN con không giao nhau và không thể rỗng trên dãy ~s~ (các ĐOẠN con cần chứa các phần tử liên tiếp nhau), sao cho cũng tồn tại ~k~ ĐOẠN con không giao nhau và không thể rỗng trên dãy ~t~ có giá trị tương tự. Bạn cần chọn ra ~k~ ĐOẠN con sao cho tổng độ dài của chúng là lớn nhất.

Note: Bạn toán này quy về đơn giản là bài toán LCS, nhưng thay vì mỗi phần tử ta lấy một kí tự, thì là lấy một đoạn con.

Input:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ ~(1 \leq n, m \leq 1000, 1 \leq k \leq 10)~, lần lượt là độ dài của chuỗi ~s~, độ dài của chuỗi ~t~, và số yêu thích của Alyona.
• Dòng thứ hai chứa chuỗi ~s~, bao gồm các chữ cái tiếng Anh viết thường.

• Dòng thứ ba chứa chuỗi ~t~, bao gồm các chữ cái tiếng Anh viết thường.

  Output:

• In ra một số nguyên không âm duy nhất — tổng độ dài của các chuỗi trong dãy mong muốn.

Ví dụ

Input 1

5 5 1
abcde
bcdea

Output 1

4

Input 2

5 5 2
abcde
bcdea

Output 2

4

Note

Ta không thể tách ra thành a và bcde, ở dưới là bcde và a (vì cần đúng thứ tự so sánh)

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Cho một số nguyên dương ~n~, hãy phân tích số ~n~ thành tổng của một số số nguyên dương sao cho bội chung nhỏ nhất của chúng là lớn nhất có thể.

Input

• Gồm một số nguyên dương ~n~, ~(1 \le n \le 340)~

Output

• In ra bội chung nhỏ nhất tìm được.

Sample Test

Input:

10

Output:

30

Giải thích: Số ~10~ được phân tích thành tổng của ~3~ số ~{2,3,5}~, bội chung nhỏ nhất của ba số đó bằng ~30~, đây là kết quả lớn nhất có thể.

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Sau khi chơi với ngọc chán chê, Tí sắp ~n~ viên ngọc ra một đường thẳng và bắt đầu nhìn ngắm chúng. Tí nhận thấy rằng có không quá ~k~ màu ngọc khác nhau trên bàn và viên ngọc thứ ~i~ từ trái sang thì có màu ~a_i~. Tí muốn chia dãy ngọc thành các đoạn liên tiếp sao cho mỗi đoạn đều có đủ ~k~ màu. Hỏi Tí có bao nhiêu cách chia thỏa mãn như vậy?

Yêu cầu: In số cách chia thỏa mãn sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~.

Output

• Ghi ra một số nguyên là kết quả bài toán.

Constraints

• ~1\leq k\leq n\leq 10^6~
• ~1\leq a_i\leq k~

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~k = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~n\leq 5000~.
• Subtask ~3~ (~20\%~ số điểm): ~n\leq 10^5, k\leq 100~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input ~1~

5 2
1 2 2 1 2 

Sample Ouput ~1~

3

Explanation

Có ~3~ cách chia như sau: ~(1\ 2) | (2\ 1\ 2), (1\ 2\ 2) | (1\ 2)~, hoặc ~(1\ 2\ 2\ 1\ 2)~.

Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua ~n~ chú cá và ~m~ bể thủy sinh. Chú cá thứ ~i~ có sức mạnh là ~a_i~

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le m \le n \le 2000)~ cho biết số chú cá và số bể thủy sinh.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 \le ai \le 10^9 )~ cho biết sức mạnh của các chú cá.

Output

• In một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Subtask

• Có ~20\%~ số test ứng với ~n \le 8~.
• Có ~20\%~ số test khác ứng với ~n \le 15~.
• Có ~20\%~ số test khác ứng với ~m = 2~.
• Có ~30\%~ số test khác ứng với ~n \le 100~.
• ~10\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

6 3
9 2 11 3 5 8

Sample Output 1

75

Sample Input 2

4 4
10 20 30 40

Sample Output 2

100

Explanation

Trong ví dụ thứ nhất, một cách đặt cá vào bể thủy sinh tối ưu như sau:

• Đặt chú cá thứ ~1, 6~ vào bể thứ nhất.
• Đặt chú cá thứ ~2, 4, 5~ vào bể thứ hai.
• Đặt riêng chú cá thứ ~3~ vào bể thứ ba. Độ bất ổn của các chú cá lần lượt là ~17 + 10 + 11 + 10 + 10 + 17 = 75~.

Ở ví dụ thứ hai, ta sẽ đặt riêng mỗi chú cá vào một bể thủy sinh.

It's not a bug — it's an undocumented feature 😈

Cho một dãy số nguyên ~A~ gồm ~n~ phần tử, được đánh số ~A_1,A_2,...,A_n~.

Ta có một số định nghĩa như sau:

• Trọng số của đoạn con (ở đây là một đoạn con liên tiếp) là tổng các giá trị ~A_i~ trong đoạn.
• Độ cân bằng của dãy ~A~ là trọng số của đoạn con có trọng số lớn nhất trong dãy số.

Bài toán sẽ thật dễ dàng nếu chỉ yêu cầu tính độ cân bằng của dãy ~A~ được cho, vậy nên ~Watermelon~ - người thầy của muôn quả - đã quyết định tăng độ khó bằng cách sau:

• Đầu tiên, thầy đưa ra một dãy số nguyên gồm ~n~ phần tử ~B_1,B_2,...,B_n~.
• Có tối đa ~k~ lượt chỉnh sửa, mỗi lượt bạn được chọn một đoạn con các phần tử từ vị trí thứ ~l~ đến vị trí thứ ~r~ ~(1 \le l \le r \le n)~ và thực hiện phép gán ~A_i = A_i*B_i~ với ~\forall i \in [l,r]~.

Yêu cầu: Đưa ra được độ cân bằng lớn nhất với tối đa ~k~ lượt chỉnh sửa.

Hoa Quả Sơn đã phải bó cành trước bài toán mới này, bạn hãy giúp họ tìm kiếm câu trả lời.

Input: watermelon.inp

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~k~ ~(1 \le n \le 10^5, 0 \le k \le 10)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~A_1, A_2, ..., A_n~ ~(|A_i| \le 1000)~.
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy số nguyên ~B_1, B_2, ..., B_n~ ~(|B_i| \le 10)~.

Output: watermelon.out

• In ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của dãy ~A~ sau khi sử dụng tối đa ~k~ lượt chỉnh sửa.

Scoring:

• Subtask ~1~ ~(15\%)~: ~k = 0~.
• Subtask ~2~ ~(15\%)~: ~k = 1~ và ~n \le 5000~.
• Subtask ~3~ ~(20\%)~: ~k = 1~.
• Subtask ~4~ ~(25\%)~: ~k = 2~.
• Subtask ~5~ ~(25\%)~: Không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

3 0
-4 -10 -8
2 2 -1

Sample Output 2

-4

Explanation:

• Trong ví dụ thứ nhất, cách tối ưu nhất là chọn đoạn ~[3, 4]~ để tác động. Như vậy dãy ~A~ mới là ~[-3, 4, 5, 4, -2]~. Vậy độ cân bằng của dãy này là ~13~.
• Trong ví dụ thứ ~2~, khi ~k = 0~, bạn không thực hiện lượt chỉnh sửa nào và đưa ra độ cân bằng của dãy ~A~ ban đầu là ~-4~.

Tiếp tục là Châu và câu chuyện hành trình trở thành thợ code của anh ấy. MrTee sau khi thấy Châu đã quá thợ nên đã gửi anh ấy cho thầy Hưng Cao dạy. Thử thách đầu tiên thầy Hưng giao cho Châu là Con cáo và chùm nho (không phải bài nhạc mà các bạn biết). Thử thách có nội dung như sau:

Cho chùm nho có ~N~ quả và ~M~ cành cây, mỗi cành cây nối 2 quả nào đó với nhau. Giữa 2 quả bất kì có thể có nhiều cành cây nối chúng (cây bị down). Cũng có thể có những quả có cành cây nối với chính nó. Đơn giản thì chùm nho là mô hình đồ thị ~N~ đỉnh, ~M~ cạnh.

Các quả nho được đánh số từ ~1~ đến ~N~. Quả thứ ~i~ có độ cao là ~A_i~. Độ dốc giữa cành cây nối giữa 2 quả được tính bằng giá trị tuyệt đối chênh lệch chiều cao giữa 2 quả nho. Ví dụ cành cây nối giữa 2 quả ~x~ và ~y~ sẽ có độ dốc là ~|A_x - A_y|~.

Dù trong nhiều câu chuyện, cáo luôn là phản diện nhưng chúng là loài động vật thông minh. Ai cũng thích động vật thông minh và Châu và thầy Hưng cũng vậy. Để giúp con cáo lấy được chuỗi các quả nho xịn và nhiều nhất, Châu phải thiết kế 1 con đường leo cây siêu nhanh. Xuất phát từ 1 quả nho nào đó, đi đến các quả nho khác với điều kiện các quả nhỏ sau cao hơn quả nho trước, không những thế, độ dốc của cành cây sau cũng phải lớn hơn độ dốc của cành cây trước đó. Nghĩa là, nếu như Châu quyết định chọn một hành trình đi qua các quả nho theo thứ tự ~P_1, P_2, ..., P_k~ thì hành trình đó sẽ phải thỏa mãn tính chất:

~0 < A_{P_2}-A_{P_1} < A_{P_3}-A_{P_2} < ... < A_{P_k}-A_{P_{k-1}}~

Như đã nói, để giúp con cáo, hành trình này cũng phải thỏa mãn việc nó có đi qua nhiều quả nho nhất. Ngoài ra thầy Hưng cũng muốn biết thêm có bao nhiêu cách đi như vậy để còn giật dây hành trình của con cáo.

Vì là thợ đặc cấp nên Châu dễ dàng vượt qua thử thách này và được dạy cho nhiều câu punchline như một phần thưởng.

Liệu bạn có thợ như Châu?

Yêu cầu:

• Tìm đường đi qua nhiều quả nho nhất và thỏa mãn yêu cầu đề bài. Đồng thời tìm xem có bao nhiêu đường đi khác nhau đi qua nhiều quả nho nhất.

Input: dincpath.inp

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~ ~(1 \le N \le 3 * 10 ^ 5, 1 \le M \le 5 * 10^5)~.
• Dòng thứ hai chứa độ cao của ~N~ quả nho là ~N~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~.
• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa cặp số nguyên dương ~(U_i, V_i)~ là chỉ số hai quả nho và là hai đầu của cành cây thứ ~i~ ~(1 \le U_i, V_i \le N)~.

Output: dincpath.out

• Dòng đầu tiên ghi ra một số nguyên là số lượng quả nho của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng hành trình khác nhau tìm được cho ~10^9 + 7~.

Subtasks

• Có ~20\%~ số test ứng với ~N \le 20~.
• Có ~20\%~ số test khác ứng với ~N \le 500~.
• Có ~20\%~ số test khác ứng với đồ thị tương ứng là một mạch thẳng (đồ thị dạng cây nhưng mỗi đỉnh chỉ có tối đa 2 cạnh).
• Có ~20\%~ số test khác ứng với ~M = N - 1~, và các đỉnh trong đồ thị liên thông với nhau.
• ~20\%~ còn lại không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

3
1

Cho số nguyên dương ~N~ và dãy hoán vị từ ~1~ đến ~N~. Hãy tính tổng chi phí nhỏ nhất để sắp xếp dãy hoán vị ban đầu thành dãy tăng dần. Biết rằng có thể chọn một dãy con liên tiếp từ ~i~ đến ~j~ và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là ~\lfloor \sqrt {j - i + 1} \rfloor~ (lấy phần nguyên, ví dụ ~\lfloor 10,3333 \rfloor = 10~).

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

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên dương là hoán vị từ ~1~ đến ~N~.

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

Chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 9;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 2000;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \leq 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thoả mãn ~N \leq 10^6.~

Ví dụ

Input

5
3 1 4 2 5

Output

2

Giải thích

Chọn dãy con ~[3, 1]~ mất chi phí ~1~ và chuyển dãy thành ~[1, 3, 4, 2, 5]~, sau đó chọn dãy con ~[3, 4, 2]~ với chi phí ~1~ để sắp xếp thành dãy ~[1, 2, 3, 4, 5]~ với tổng chi phí là ~2~.

Cho một đa giác lồi gồm ~n~ đỉnh trên hệ trục tọa độ ~OXY~. Các điểm được đánh số từ ~p_1,p_2,...,p_n~.

Với mỗi điểm ~p_i~ ~(1 \le i \le n)~, hãy xác định chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~. Các điểm được cho theo chiều ngược kim đồng hồ.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~. Kết quả làm tròn đến số thứ ~4~ sau dấu phẩy.

Constraints .

• ~1 \le n \le 1000~.
• ~|x_i|,|y_i| \le 10^9~.

Subtask

• Sub ~1~ (~30\%~): ~n \le 10~.
• Sub ~2~ (~30\%~): ~n \le 100~.
• Sub ~3~ (~40\%~): ~n \le 1000~.

Sample Input 1

8
0 3
1 1
3 0 
6 2
5 5
3 6
1 5
5 0

Sample Output 1

27.3183
26.8052
27.3183
27.3183
27.2445
27.3183
27.3183
27.3183