Cho mảng A[] gồm N số nguyên không âm và số K. Nhiệm vụ của bạn là hãy chia mảng A[] thành hai mảng con có kích cỡ K và N-K sao cho hiệu giữa tổng hai mảng con là lớn nhất. Ví dụ với mảng A[] = {8, 4, 5, 2, 10}, K=2 ta có kết quả là 17 vì mảng A[] được chia thành hai mảng {4, 2} và { 8, 5, 10} có hiệu của hai mảng con là 23-6=17 là lớn nhất.

Đầu vào: Dòng duy nhất chứa 2 số nguyên N và K; Dòng thứ 2 gồm N số của mảng A[]

Ràng buộc: 1<=K<=N<=10^6; 0<=A[i]<=10^9;

Đầu ra: In ra đáp án của bài toán

Input:

6 4
3 10 10 7 5 2

Output:

27

Cho 2 dãy A và B đã sắp xếp tăng dần. Bạn hãy thực hiện trộn 2 dãy A và B thành 1 dãy C cũng sắp xếp tăng dần.

Ràng buộc: Ràng buộc: ~1 \leq N \leq 2.10^6~; ~-10^6 \leq A[i], B[i] \leq 10^6~

Input:

5
1 3 5 6 9
3
2 7 8

Output:

1 2 3 5 6 7 8 9

Cho 2 xâu S và T, tìm xâu con ngắn nhất của S chứa đầy đủ và đúng thứ tự các ký tự trong T.

Ràng buộc: ~1 \leq len(T), len(S) \leq 10^3~

S, T chứa các ký tự in thường

In ra độ dài xâu con nhỏ nhất thỏa mãn, nếu không có xâu nào thỏa mãn in ra NOT FOUND

Input 01:

hoccohocnngnghehnc
hcn

Output 01:

4

Input 02:

hoccohocnngnghehnc
hwn

Output 02:

NOT FOUND