Có N viên ngọc được xâu thành một vòng cổ hình tròn (viên thứ 1 kề với viên thứ 2, ..., viên thứ N kề với viên thứ 1). Viên ngọc thứ i có giá trị là V_i. Bạn được phép lấy ra một số viên ngọc để bán, nhưng do hệ thống báo động, bạn tuyệt đối không được lấy 2 viên ngọc nằm kề nhau trên vòng cổ. Hãy tìm cách chọn ngọc sao cho tổng giá trị thu được là lớn nhất.

Input:

Dòng 1: N (3 <= N <= 10^5).

Dòng 2: N số nguyên Vi (1 <= Vi <= 10^4).

Output: Tổng giá trị lớn nhất.

Ví dụ:

Input:

4
1 2 3 1

Output:

4

(Giải thích: Chọn viên thứ 2 và thứ 4, tổng = 2 + 1 = 3. Hoặc viên 1 và 3, tổng = 1 + 3 = 4).

Một nông trường chè tại Thái Nguyên có N luống chè, luống thứ i cho sản lượng A_i kg. Để thử nghiệm một loại phân bón mới, kỹ sư nông nghiệp cần chọn một dải gồm ít nhất K luống chè liên tiếp nhau sao cho "sản lượng trung bình" của dải này là lớn nhất có thể. Hãy tìm mức sản lượng trung bình cực đại đó.

Input:

Dòng 1: N, K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Output: Sản lượng trung bình lớn nhất (in ra phần nguyên làm tròn xuống của kết quả).

Ví dụ:

Input:

4 2
8 1 9 10

Output:

9

(Giải thích: Chọn đoạn [9, 10] có độ dài 2 >= K, trung bình là 9.5. Làm tròn xuống là 9).

Khác với bài toán xâu con chung dài nhất (không cần liên tiếp), các nhà sinh học đang cần tìm đoạn gen chung liên tiếp dài nhất xuất hiện trong cả hai chuỗi gen A và B. Hãy tìm và in ra độ dài của đoạn gen chung liên tiếp cực đại đó.

Input:

Dòng 1: Xâu A (độ dài <= 2000).

Dòng 2: Xâu B (độ dài <= 2000).

Output: Độ dài chuỗi con liên tiếp chung dài nhất.

Ví dụ:

Input:

abcdxyz
cdeabcdx

Output:

5

(Giải thích: Đoạn chung liên tiếp dài nhất là abcdx).

Là một freelancer, bạn nhận được danh sách N dự án. Dự án thứ i mang lại thù lao Pi nhưng bắt buộc phải hoàn thành trước thời điểm Di (nếu thời điểm hiện tại t > D_i thì không thể nhận). Biết rằng mỗi dự án đều tốn đúng 1 đơn vị thời gian để hoàn thành, và bạn chỉ có thể làm 1 dự án tại 1 thời điểm (bắt đầu từ thời điểm 1). Hãy chọn ra các dự án để làm sao cho tổng thù lao thu được là lớn nhất.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng gồm 2 số nguyên Di, Pi (1 <= Di <= 10^5, 1 <= Pi <= 10^4).

Output: Tổng thù lao lớn nhất.

Ví dụ:

Input 01:

4
4 20
1 10
1 40
1 30

Output 01:

60

(Giải thích: Chọn dự án thù lao 40 làm vào thời điểm 1, dự án thù lao 20 làm vào thời điểm 2. Không thể chọn cả dự án 40 và 30 vì chúng đều có deadline là 1).

Input 02:

3
1 10
2 30
2 60

Output 02:

90

Một dãy số được gọi là "dãy núi" nếu nó tăng ngặt lên đến một đỉnh rồi giảm ngặt xuống (ví dụ 1 3 5 4 2). Cho dãy A gồm N số nguyên, bạn hãy tìm cách xóa đi một số phần tử để các phần tử còn lại giữ nguyên thứ tự tạo thành một "dãy núi" dài nhất. In ra độ dài lớn nhất đó.

Input:

Dòng 1: N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).

Output: Độ dài của dãy con Bitonic dài nhất.

Ví dụ:

Input:

6
1 5 2 4 2 1

Output:

5

(Giải thích: Dãy con chọn là 1 5 4 2 1).

Một dãy gồm N đống quặng kim loại được xếp thành hàng ngang, đống thứ i có khối lượng W_i. Bạn cần gộp tất cả chúng lại thành 1 đống duy nhất. Mỗi lần gộp, bạn chỉ được phép gộp 2 đống quặng nằm kề nhau thành 1 đống mới, và chi phí cho lần gộp đó bằng tổng khối lượng của 2 đống quặng. Hãy tìm cách gộp sao cho tổng chi phí của tất cả các lần gộp là nhỏ nhất.

Input:

Dòng 1: N (1 <= N <= 400).

Dòng 2: N số nguyên Wi (1 <= Wi <= 100).

Output: Tổng chi phí nhỏ nhất.

Ví dụ:

Input:

4
1 3 5 2

Output:

22

(Giải thích: Gộp 1+3=4 (chi phí 4). Dãy còn: 4 5 2. Gộp 5+2=7 (chi phí 7). Dãy còn: 4 7. Gộp 4+7=11 (chi phí 11). Tổng chi phí = 4 + 7 + 11 = 22).