Quy hoạch động

Cho dãy số nguyên \(A\) gồm \(n\) phần tử \(A_1, A_2, \dots, A_n\).

Một dãy con tăng ngặt của \(A\) là dãy được tạo ra bằng cách chọn ra một hoặc nhiều phần tử từ dãy ban đầu (giữ nguyên thứ tự xuất hiện) sao cho phần tử đứng sau luôn lớn hơn phần tử đứng trước nó.

Hãy tìm một dãy con tăng ngặt của dãy \(A\) sao cho tổng các phần tử được chọn đạt giá trị lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2000\)) là số lượng phần tử của dãy.
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^9\)), các số cách nhau bởi một khoảng trắng.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất của dãy con tăng ngặt tìm được.

Example

5
1 101 2 3 100

106

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(n \le 2000\)

Cho hai xâu ký tự \(S\) và \(T\). Hãy tìm độ dài của xâu con chung dài nhất (Longest Common Subsequence - LCS) của hai xâu này.

(Lưu ý: Xâu con của một xâu được tạo ra bằng cách xóa đi một vài ký tự (hoặc không xóa ký tự nào) từ xâu ban đầu mà không làm thay đổi thứ tự của các ký tự còn lại. Xâu con chung không bắt buộc phải gồm các ký tự liên tiếp nhau).

Input

• Dòng đầu tiên chứa xâu \(S\) (\(1 \le \vert{}S\vert{} \le 2000\)).
• Dòng thứ hai chứa xâu \(T\) (\(1 \le \vert{}T\vert{} \le 2000\)).

Output

• In ra một số nguyên duy nhất là độ dài của xâu con chung dài nhất của \(S\) và \(T\).

Example

ABCBDAB
BDCABA

4

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(\vert{}S\vert{}, \vert{}T\vert{} \le 2000\)

Cho một xâu ký tự \(S\). Hãy tìm độ dài của xâu con liên tiếp đối xứng dài nhất (Longest Palindromic Substring) của xâu \(S\).

(Lưu ý: Xâu con liên tiếp là một chuỗi các ký tự nằm liền kề nhau trong xâu ban đầu. Xâu đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái đều giống hệt nhau).

Input

• Một dòng duy nhất chứa xâu \(S\) (\(1 \le \vert{}S\vert{} \le 2000\)).

Output

• In ra một số nguyên duy nhất là độ dài của xâu con liên tiếp đối xứng dài nhất.

Example

babad

3

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(\vert{}S\vert{} \le 2000\)

Cho dãy số nguyên \(A\) gồm \(n\) phần tử và một số nguyên \(S\). Hãy đếm số lượng dãy con (subsequence) của \(A\) sao cho tổng các phần tử trong dãy con đó bằng đúng \(S\).

(Lưu ý: Dãy con được tạo ra bằng cách chọn ra một số phần tử từ dãy ban đầu mà không cần liên tiếp (giữ nguyên thứ tự vị trí). Các cách chọn tập hợp vị trí khác nhau sẽ tính là các dãy con khác nhau).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(S\) (\(1 \le n \le 2000\), \(1 \le S \le 2000\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 2000\)).

Output

• In ra một số nguyên duy nhất là số lượng dãy con có tổng bằng \(S\).

Example

4 5
1 2 3 2

3

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(n, S \le 2000\)

Cho \(n\) đồ vật, mỗi vật có trọng lượng là \(w_i\) và giá trị là \(v_i\). Một chiếc túi có sức chứa tối đa là \(W\). Mỗi đồ vật chỉ được chọn tối đa một lần. Hãy chọn các đồ vật đưa vào túi sao cho tổng trọng lượng không vượt quá \(W\) và tổng giá trị thu được là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(W\) (\(1 \le n \le 100\), \(1 \le W \le 100000\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i\) và \(v_i\) lần lượt là trọng lượng và giá trị của đồ vật thứ \(i\) (\(1 \le w_i, v_i \le 10^5\)).

Output

• In ra một số nguyên duy nhất là tổng giá trị lớn nhất có thể đạt được.

Example

3 8
3 30
4 50
5 60

90

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(n \le 100\), \(W \le 10^5\).

Khu rừng là một bảng \(n \times n\). Từ ô \((i, j)\), Nam có thể đi đến ô \((i + 1, j)\) hoặc \((i, j + 1)\).

Ô \((i, j)\) có \(A_{i, j}\) cây nấm. Hành trình của Nam bắt đầu từ \((1, 1)\) và kết thúc tại \((n, n)\), số nấm tối đa cô ấy có thể thu thập được là bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 1000\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả bảng \(A\), trong đó số thứ \(j\) ở dòng thứ \(i\) là \(A_{i, j}\) (\(1 \le A_{i, j} \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số nấm tối đa Nam có thể thu thập được.

Example

4
2 2 2 1
1 1 2 1
1 1 2 1
1 1 2 2

14

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(1 \le n \le 1000\), \(1 \le A_{i, j} \le 10^9\).

Bạn đang quản lí một hội trường. Có \(n\) lượt đăng kí sử dụng hội trường, lượt thứ \(i\) là \([l_i, r_i]\), đăng kí sử dụng hội trường trong khoảng thời gian từ \(l_i\) đến \(r_i\), tổng thời gian sử dụng là \(r_i - l_i + 1\).

Tại một thời điểm, chỉ được tiếp nhận nhiều nhất một lượt đăng kí. Ví dụ hai lượt đăng kí \([3, 5]\) và \([5, 7]\) không thể thực hiện được cùng một lúc do trùng thời điểm \(5\). Nhiệm vụ của bạn là chọn ra một số lượt đăng kí sao cho không tồn tại hai lượt đăng kí có thời gian giao nhau và tổng thời gian sử dụng hội trường là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• \(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(l_i, r_i\).

Output

• In ra một số nguyên là tổng thời gian sử dụng hội trường nhiều nhất.

Example

4
1 3
2 5
4 6
6 8

7

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le n \le 20\), \(1 \le l_i, r_i \le 10^5\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 1000\), \(1 \le l_i, r_i \le 10^5\).
• Subtask \(3\) (\(50\%\) số điểm): \(1 \le n \le 10^5\), \(1 \le l_i, r_i \le 10^5\).