Chuyên đề. DP - Qui hoạch động cơ bản.

Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau \(n\) tháng có bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh

Trong hình vẽ trên, ta quy ước:

• Cặp thỏ nâu là cặp thỏ có độ tuổi \(1\) tháng.
• Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.

Nhìn vào hình vẽ trên ta nhận thấy:

• Tháng Giêng và tháng Hai: Chỉ có \(1\) đôi thỏ.
• Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có \(2\) đôi thỏ.
• Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có \(3\) đôi thỏ.
• Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có \(2 + 3 = 5\) đôi thỏ.
• Tháng Sáu: có ba đôi thỏ (\(2\) đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có \(3 + 5 = 8\) đôi thỏ.

Khái quát, nếu \(n\) là số tự nhiên khác \(0\), gọi \(f(n)\) là số đôi thỏ có ở tháng thứ \(n\), ta có:

• Với \(n=1\) ta được \(f(1)=1\).
• Với \(n=2\) ta được \(f(2)=1\).
• Với \(n=3\) ta được \(f(3)=2\).
• Do đó với \(n>2\) ta được: \(f(n)=f(n−1)+f(n−2)\).

Nguồn: wikipedia

Dãy số trên gọi là dãy số \(Fibonacci\) và được định nghĩa như sau:

• \(F_1=F_2=1;\)
• \(\dots\)
• \(F_n=F_{n−2}+F_{n−1}\)

Hãy viết chương trình tính các số \(Fibonacci\) thứ \(a[i]\).

Input

• Gồm \(T\) dòng (\(T \le 10^6\)), dòng thứ \(i\) chứa số \(a[i]\) (\(a[i] \le 1000\)).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) chứa số \(F_{a[i]}\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T = 5\) và \(a[i] \le 75\).
• Subtask \(2\) (\(25\%\) số điểm): \(a[i] \le 75\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
2
7
24
31
1 

1
1
13
46368
1346269
1

Nhiệm vụ của bạn là đếm số cách tạo ra tổng \(n\) bằng cách gieo xúc xắc một hoặc nhiều lần. Mỗi lần gieo cho ra số từ \(1\) đến \(6\).

Ví dụ, nếu \(n = 3\), có \(4\) cách:

• \(1 + 1 + 1\)
• \(1 + 2\)
• \(2 + 1\)
• \(3\)

Input

• Dòng đầu vào duy nhất có số nguyên \(n\).
• Giới hạn: \(1 \leq n \leq 10^6\)

Output

• In số cách chia lấy dư cho \(10^9 + 7\).

Example

3

4

Hãy xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn sao cho số lượng đồng xu là tối thiểu.

Ví dụ: nếu các đồng xu là \(\{1,5,7\}\) và tổng mong muốn là \(11\), một giải pháp tối ưu là \(5 + 5 + 1\), cần \(3\) đồng xu.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn
• Dòng thứ hai có \(n\) số nguyên phân biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Output

• In một số nguyên: số lượng đồng xu tối thiểu. Nếu không thể tạo ra tổng mong muốn, hãy in \(-1\)

Example

3 11
1 5 7

3

Hãy xem xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tính số lượng các cách khác nhau mà bạn có thể tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(8\) cách:

• \(2+2+5\)
• \(2+5+2\)
• \(5+2+2\)
• \(3+3+3\)
• \(2+2+2+3\)
• \(2+2+3+2\)
• \(2+3+2+2\)
• \(3+2+2+2\)

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn.
• Dòng thứ hai có \(n\) số nguyên phân biệt biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

• In một số nguyên: số lượng cách, chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Example

3 9
2 3 5

8

Xét một hệ thống tiền tệ với \(n\) loại đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Hãy tính số cách khác nhau, không kể thứ tự để tạo ra tổng tiền \(x\) từ những đồng này.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(3\) cách:

• \(2+2+5\)
• \(3+3+3\)
• \(2+2+2+3\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn
• Dòng thứ hai chứa \(n\) số nguyên riêng biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Output

• In một số nguyên duy nhất: số lượng cách, chia lấy dư cho \(10^9 + 7\)

Example

3 9
2 3 5

3

Bạn được cho một số nguyên \(n\). Ở mỗi bước, bạn có thể trừ \(n\) đi một lượng bằng một trong các chữ số của nó.

Cần bao nhiêu bước để làm cho \(n\) bằng \(0\)?

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) \((1 \leq n \leq 10^6)\).

Output

• In ra một số nguyên duy nhất là số bước tối thiểu cần dùng.

Example

27

5

Xét một lưới ô vuông kích thước \(n \times n\), trong đó một số ô có thể có bẫy. Ta không được phép đi qua một ô có bẫy.

Hãy tính số lượng đường đi từ góc trên trái đến góc dưới phải của lưới, biết rằng ta chỉ được đi sang phải hoặc đi xuống dưới.

Input

• Dòng đầu tiên chứa một số nguyên \(n\): kích thước của lưới.
• \(n\) dòng sau, mỗi dòng chứa \(n\) kí tự mô tả lưới: . biểu thị một ô trống và * biểu thị một cái bẫy.

Output

• In ra một số nguyên duy nhất là số lượng đường đi chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \leq n \leq 1000\)

Example

4
....
.*..
...*
*...

3

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị tối đa của một đoạn con khác rỗng.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị của mảng.

Output

• In một số nguyên duy nhất là tổng đoạn con lớn nhất.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(-10^9 \leq x_i \leq 10^9\)

Example

8
-1 3 -2 5 3 -5 2 2

9

Có \(N\) hòn đá được đánh số từ \(1,2,\ldots,N\). Hòn đá thứ \(i\) có chiều cao là \(h_i\).

Ban đầu, có một con ếch đang ngồi ở hòn đá thứ nhất. Con ếch sẽ lặp đi lặp lại thao tác sau nhiều lần để đến được hòn đá thứ \(N\):

• Nếu con ếch đang ở hòn đá thứ \(i\), nó có thể nhảy đến hòn đá thứ \(i+1\) hoặc hòn đá thứ \(i+2\) với chi phí là \(|h_i-h_j|\) (\(j\) là hòn đá mà con ếch nhảy đến).

Bạn hãy giúp con ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất tới hòn đá thứ \(N\) nhé.

Input

• Dòng thứ nhất chứa một số nguyên dương \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1,h_2,\ldots,h_N\) (\(1 \leq h_i \leq 10^4\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Example

4
10 30 40 20

30

2
10 10

0

Có \(N\) hòn đá, được đánh số từ \(1, 2, ..., N\). Độ cao của hòn đá thứ \(i\) là \(h_i\).

Có một con ếch ban đầu ở hòn đá thứ \(1\). Nó sẽ lặp lại các thao tác sau nhiều lần để tới được hòn đá thứ \(N\).

• Nếu con ếch đang ở hòn đá thứ \(i\), nó có thể nhảy đến hòn đá thứ \(i + 1, i + 2, ..., i + K\). Với chi phí cho mỗi lần nhảy là \(|h_i - h_j|\) (\(j\) là hòn đá mà con ếch nhảy đến)

Bạn hãy giúp con ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất tới hòn đá thứ \(N\) nhé.

Input

• Dòng 1: Ghi hai số nguyên \(N\) và \(K\) (\(2 \leq N \leq 10^5\), \(1 \leq K \leq 100\)).
• Dòng 2: ghi \(N\) số nguyên dương \(h_1, h_2, ..., h_N\) (\(1 \leq h_i \leq 10^4\)).

Output

• Ghi một số nguyên duy nhất là chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ \(N\).

Example

5 3
10 30 40 50 20

30

3 1
10 20 10

20

Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm \(n\) bậc.

Các bậc thang được đánh số từ \(1\) đến \(n\) từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số \(1\) (bậc thang số \(1\) không bao giờ bị thủng).

Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ \(n\)). Bờm muốn nhờ bạn trả lời câu hỏi này.

Input

• Dòng đầu tiên chứa 2 số nguyên \(n\) và \(k\), là số bậc của cầu thang và số bậc thang bị hỏng (\(0 \leq k < n \leq 10^5\)).
• Dòng thứ hai chứa \(k\) số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.

Output

• In ra phần dư của số cách Lucky leo hết cầu thang khi \(Modulo\) cho \(14062008\).

Example

4 2
2 3

0

90000 1
49000

4108266

Nguồn: vn.spoj

Bờm đang nghiên cứu mực nước biển ở hành tinh Quạt Mo. Sau nhiều ngày theo dõi, Bờm nhận thấy rằng quy luật của mực nước biển là: mực nước biển của một ngày bất kì bằng trung bình cộng mực nước biển của ngày hôm trước và ngày hôm sau. Dựa vào ghi chép mực nước biển hai ngày đầu của Bờm, hãy tính toán mực nước biển ngày thứ \(N\).

Input

• Dòng 1: chứa 2 số nguyên \(b, a\) là mực nước biển 2 ngày đầu (\(-100 \le a, b \le 100\)). Số \(a\) là mực nước ngày thứ nhất, số \(b\) là mực nước ngày thứ 2.
• Dòng 2: chứa số nguyên dương \(N\) (\(3\le N\le 10^{12}\)).

Output

• Mực nước biển ngày thứ \(N\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n\le 10^7\)
• Subtask \(2\) (\(50\%\) số điểm): \(10^7<n\le 10^{12}\)

Example

1 2
3

3

3 1
​3

-1

\(F_1 = F_2=1\)

\(F_n=F_{n-1}+F_{n-2}\) với \(n > 2\)

Tính \(F_n\)

Input

• Số test \(t (t \le 5)\)
• \(t\) dòng, mỗi dòng 1 số nguyên dương \(n (n \le 50)\)

Output

• \(t\) dòng, \(F_n\)

Example

3
1
2
3 

1
1
2

Nhập vào \(n\), in ra \(n\) số fibo đầu tiên.

Dãy Fibonacci \(1, 1, 2, 3, 5, 8, .....\)

Example

4

1 1 2 3

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^9)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^3)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

Cho một dãy số nguyên gồm N phần tử \(A[1], A[2], ... A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],... A[i_k]\) thỏa mãn
\(i_1 < i_2 < ... < i_k\) và \(A[i_1] < A[i_2] < .. < A[i_k]\).

Yêu cầu:

• Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 ≤ N ≤ 1000\))
• Dòng thứ 2 ghi N số nguyên \(A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 1000000)\).

Kết quả

• Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

6
1 2 5 4 6 2

4

Nguồn: vn.spoj

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

• Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
• Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

• Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Example

6
1 2 5 4 6 2 

4

Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là xác định dãy con tăng dài nhất của mảng, tức là, tìm dãy con dài nhất trong đó tất cả các phần tử đều lớn hơn phần tử trước đó.

Một dãy con là một dãy có thể thu được từ mảng bằng cách xóa một số phần tử mà vẫn không thay đổi thứ tự của các phần tử còn lại.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) - kích thước của mảng
• Sau đó có \(n\) số nguyên \(x_1, x_2, \dots, x_n\) \((1 \leq x_i \leq 10^9)\) - các phần tử của mảng

Output

• In độ dài của dãy con tăng dài nhất

Example

8
7 3 5 3 6 2 9 8

4

Bạn đang ở trong một hiệu sách bán \(n\) cuốn sách khác nhau. Bạn biết giá và số trang của mỗi cuốn sách.

Bạn quyết định tổng số tiền mua sách của bạn tối đa là \(x\). Tổng số trang tối đa bạn có thể mua là bao nhiêu? Bạn chỉ có thể mua mỗi cuốn sách nhiều nhất một lần.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng sách và tổng số tiền tối đa
• Dòng tiếp theo chứa \(n\) số nguyên \(h_1,h_2,\ldots,h_n\): giá cả của mỗi cuốn sách
• Dòng cuối cùng chứa \(n\) số nguyên \(s_1,s_2,\ldots,s_n\): số trang của mỗi cuốn sách

Constraints

• \(1 \leq n \leq 1000\)
• \(1 \leq x \leq 10^5\)
• \(1 \leq h_i,s_i \leq 1000\)

Output

• In một số nguyên duy nhất: tổng số trang tối đa

Example

4 10
4 8 5 3
5 12 8 1

13

Năm ngoái Conan chỉ mới bước vào học Tin học thật sự. Thế nhưng anh ta bị đàn em là Như Quỳnh thách đố bài toán sau:

Cho \(T \leq 10^5\) dòng. Mỗi dòng của \(T\) có \(1\) số \(N\) (\(N \leq 10^5\)).

Dãy số \(A\) được xây dựng như sau:

• \(A[0] = 0\)
• \(A[1] = 1\)
• \(A[2i] = A[i]\)
• \(A[2i+1] = A[i] + A[i+1]\)

Yêu cầu: Nhiệm vụ của bạn là tìm số lớn nhất của dãy \(A\) từ \(1\) tới \(N\).

Input

• Dòng đầu tiên là số \(T\).
• \(T\) dòng sau, mỗi dòng là 1 số \(N\).

Output

• Có \(T\) dòng tương ứng với giá trị lớn nhất của các đoạn.

Example

2
5
10

3
4

Nguồn: vn.spoj

Kì nghỉ hè của Taro sẽ bắt đầu vào ngày mai và cậu bé đã quyết định lên kế hoạch cho kì nghỉ ngay từ bây giờ.

Kì nghỉ gồm \(N\) ngày. Ngày thứ \(i\), Taro sẽ chọn một trong các hoạt động sau:

• A: Bơi ở biển. Đạt được \(a_i\) điểm hạnh phúc.
• B: Bắt côn trùng trên núi. Đạt được \(b_i\) điểm hạnh phúc.
• C: Làm bài tập về nhà. Đạt được \(c_i\) điểm hạnh phúc.

Vì Taro dễ chán nên cậu bé không thể làm cùng một hoạt động trong 2 ngày liên tiếp trở lên.

Hãy tính điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Input

• Dòng đầu: Ghi số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng ghi \(3\) số nguyên \(a_i, b_i, c_i\) (\(1 \leq a_i, b_i, c_i \leq 10^4\)).

Output

• Ghi một số nguyên duy nhất là tổng điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Example

3
10 40 70
20 50 80
30 60 90

210

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

46

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

• Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
• Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.

Input

• Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
  • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

• Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

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

10 10
9 7

Cho một dãy gồm \(n\) số nguyên \(A=(a_1,a_2,…,a_n)\). Ta định nghĩa: đoạn con của dãy \(A\) là một dãy các phần tử liên tiếp nhau thuộc \(A\). Hoặc có thể viết \((a_i,a_{i+1},…,a_j)\) là một đoạn con của \(A\) với \(i \leq j\). Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là \(j-i+1\).

Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy \(A\).

Input

• Dòng đầu chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,….,a_n\).

Output

• Một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài.

Example

8
1 3 6 2 8 1 3 8 

2

Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường \('a'..'z'\). Tìm xâu con chung dài nhất (subsequence) của hai xâu \(s\) và \(t\)

Input

• Dòng thứ nhất chứa xâu \(s(1\le |s|\le 3000)\)

• Dòng thứ hai chứa xâu \(t(1\le |t|\le 3000)\)

Output

• In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

axyb
abyxb

axb

Tiền sĩ Hùng là một nhà nghiên cứu về các con số. Đề tài lần này ông được giao nhiệm vụ tìm ra một bài toán để kiểm tra năng lực của các học viên trong phòng thí nghiệm của ông. Nhưng tất cả các học viên của ông đều rất thông minh nên để thử tài họ phải là một bài toán cực khó. Con trai của ông năm nay vào lớp 3. Do ảnh hưởng của bố nên cậu ta cũng rất hứng thú với những con số. Trong khi Hùng đang nát óc nghĩ bài toán thì con trai của ông chỉ vào đống tài liệu về các dãy bit gồm toàn số \(0, 1\) và khoái chí nói rằng: “Ba ơi, đoạn bit này có \(5\) số \(0\) và \(5\) số \(1\) ba ạ. Con rất thích những thứ cân bằng như thế !!”. Cậu con trai vừa dứt lời, Hùng liền nghĩ ngay ra bài toán để thách đố học viên của mình. Quả nhiên sau đó tât cả đều chịu thua trước bài toán hóc búa này. Các bạn hãy giúp các bạn học viên giải quyết bài toán của Tiến sĩ Hùng nhé!!!! Bài toán như sau: “Cho dãy số \(A\) gồm \(N\) phần tử \(0\) hoặc \(1\). Tìm đoạn con liên tiếp dài nhất mà trong đó có số lượng số \(0\) và số lượng số \(1\) là như nhau”.

Input

• Dòng đầu tiên chứa \(1\) số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1},A_{2},...,A_{N}\).

Output

• Một dòng ghi một số nguyên duy nhất là kết quả của bài toán.

Constraints

• \(1 \leq n \leq 10^{5}\)
• \(0 \leq A_{i} \leq 1\)

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \leq 10^{3}\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 1 0 0 1 

4

10
1 0 0 1 1 1 0 1 1 0 

6

4
1 1 1 1 

0

Sau khi hoàn thành khóa học phi công một cách xuất sắc với số điểm cao nhất, \(xmhdang\) - zipdang04 nhận được học bổng kèm theo chứng chỉ hành nghề. Với chứng chỉ hành nghề phi công trong tay, \(xmhdang\) mong muốn lái những chiếc máy bay hiện đại nhất của các nhà sản xuất mới ra lò. Nhưng những chiếc máy bay này rất khó lái mà kinh nghiệm của \(xmhdang\) chưa nhiều. Để điều khiển được máy bay này phải qua nhiều công đoạn đúng quy trình, các công đoạn này được biểu diễn thành một xâu ký tự chỉ chứa các ký tự từ a đến z, mỗi công đoạn là một ký tự. Với phi công trẻ thiếu kinh nghiệm như \(xmhdang\) thì những công đoạn này hoặc bị thừa, hoặc bị thiếu, hoặc sai trình tự. Hỏi có cách nào để giúp \(xmhdang\) bỏ đi những đoạn bay thừa để đạt được công đoạn điều khiển máy bay đúng quy trình hay không.
Yêu cầu: Cho hai xâu \(a\) và \(b\) (\(1<|b|<|a|<10000\), |a| là độ dài của xâu \(a\)) tương ứng là biểu diễn các công đoạn của \(xmhdang\) và các công đoạn đúng. Hãy bỏ đi các công được thừa để đạt được công đoạn điều khiển máy bay đúng quy trình. Nếu được thì in ra YES, nếu không in ra NO.

Input

• Dòng thứ nhất chứa xâu \(a\);
• Dòng thứ hai chứa xâu \(b\).

Output

• 1 dòng duy nhất chứa chữ YES hoặc NO.

Example

abzefgh
aef 

YES

Bạn có \(n\) đồng xu với các giá trị nhất định. Nhiệm vụ của bạn là tìm tất cả các khoản tiền bạn có thể tạo bằng những đồng xu này.

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đồng xu
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): giá trị của các đồng xu

Constraints

• \(1 \leq n \leq 100\)
• \(1 \leq x_i \leq 1000\)

Output

• Dòng đầu tiên in ra một số nguyên \(k\): số lượng khoản tiền khác nhau có thể tạo
• Dòng tiếp theo in ra \(k\) số nguyên: các khoản tiền có thể tạo được, theo thứ tự tăng dần

Example

4
4 2 5 2

9
2 4 5 6 7 8 9 11 13

Cho ma trận gồm \(H\) hàng và \(W\) cột. Gọi \((i,j)\) là ô vuông ở hàng thứ \(i\) và cột thứ \(j\).

Với mỗi \(i,j(1\le i\le H,1\le j\le W)\), ô vuông \((i,j)\) được mô tả bởi kí tự \(a_{i,j}\). Nếu \(a_{i,j}=\). thì ô vuông này trống rỗng, nếu \(a_{i,j}=\) # thì ô vuông này chứa vật cản.

\(Kaninho\) bắt đầu ở ô vuông \((1,1)\) và muốn đến ô vuông \((H,W)\) bằng việc lặp lại các bước: Đi sang phải hoặc đi xuống dưới ô trống kề với nó.

Tìm số con đường mà \(Kaninho\) có thể đi được từ ô \((1,1)\) đến ô \((H,W)\). Bởi vì đáp án có thể lớn, nên trước khi in ra cần lấy mod \(10^9+7\).

Input

• Dòng thứ nhất chứa hai số nguyên \(H,W(2\le H,W\le 1000)\)

• \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) kí tự \(a_{i,1},a_{i,2},...,a_{i,W}(1\le i\le H)\) - thể hiện ma trận \(Kaninho\) cần đi. Biết rằng đề ra luôn đảm bảo các ô \((1,1)\) và \((H,W)\) đều trống.

Output

• In ra đáp án cần tìm.

Example

3 4
...#
.#..
....

3

Có \(N\) người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ \(1\) đến \(N\) theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết \(t_i\) là thời gian cần thiết để người \(i\) mua xong vé cho mình. Nếu người \(i+1\) rời khỏi hàng và nhờ người \(i\) mua hộ vé thì thời gian để người thứ \(i\) mua được vé cho cả hai người là \(r_i\).

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Input

• Dòng đầu tiên chứa số \(N\) (\(1 \leq N \leq 6 \times 10^4\)).
• Dòng thứ hai ghi \(N\) số nguyên dương \(t_1, t_2, ..., t_N\). (\(1 \leq t_i \leq 30000\))
• Dòng thứ ba ghi \(N-1\) số nguyên dương \(r_1, r_2, ..., r_{N-1}\). (\(1 \leq r_i \leq 30000\))

Output

In ra tổng thời gian phục vụ nhỏ nhất.

Example

5
2 5 7 8 4
4 9 10 10

18

4
5 7 8 4
50 50 50

24

Nguồn: vn.spoj

Cho số nguyên dương \(n\). Gọi \(s\) là số nguyên dương nhỏ nhất có chính xác \(n\) ước (ở đây ta chỉ tính ước dương).

Yêu cầu: Cho số nguyên dương \(n\). In ra \(s\) (Biết rằng: Đề ra đảm bảo \(s\le 10^{18}\))

Input

• Một dòng duy nhất chứa số nguyên \(n(1\le n\le 1000)\)

Output

• In ra \(s\) cần tìm

Example

2

2

Cho dãy \(a\) gồm \(n\) phần tử \(a_1,a_2,...,a_n\). Hãy in ra độ dài của dãy con gồm các phần tử liên tiếp không giảm dài nhất.

Input

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,..,a_n(1\le a_i\le 10^9)\)

Output

• Một dòng duy nhất chứa kết quả cần tìm

Example

3
4 2 3

2

Cho dãy gồm \(N (1 \le N \le 10^5)\) số nguyên \(A_1, A_2, ... , A_N (0 < A_i \le 10^5)\)

Với bộ ba số \((i,j, k)\) trong đó \(1 \le i < j < k \le n\) hãy tìm giá trị \(S = 3A_i + 2A_j − 5A_k\) sao cho \(S\) đạt
giá trị lớn nhất.

Input

Đọc từ file văn bản BOBASO.INP gồm hai dòng:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ... , A_N\) giữa các số cách nhau một khoảng trắng.

Output

• Ghi ra file văn bản BOBASO.OUT một số duy nhất là số \(S\) lớn nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 100\)
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 5.10^3\)
• Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5\)

Example

10
4 9 7 9 4 3 2 9 15 6

35

Sau những giờ thi HSG căng thẳng, BTC tổ chức cho các thí sinh gặp nhau và tham gia các trò chơi giải trí. Trong nội dung phóng phi tiêu, trước khi vào vị trí người chơi được BTC cho quan sát \(N\) ô được đánh số từ \(1\) đến \(N\), trên mỗi ô ghi một số nguyên dương tương ứng với điểm có được nếu người chơi phóng tiêu trúng. Tại mỗi thời điểm người chơi chỉ có thể phóng \(1\) cây tiêu và theo nguyên tắc người chơi không được phóng vào \(3\) ô liên tiếp nhau.

Yêu cầu: Hãy viết chương trình giúp người chơi chọn các ô để phóng sao cho tổng điểm thu được là lớn nhất. Giả sử tỷ lệ phóng trúng là \(100\)%.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1\le n\le 10^6\))
• Các dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là số điểm ghi trên các ô (\(0< a_i\le 10^9\))

Output

• Một dòng ghi số điểm lớn nhất tìm được.

Example

4
9 3 5 4

18

ami có một dãy số nguyên dương \(A\) gồm \(n\) phần tử và một dãy số nguyên dương \(B\) gồm \(m\) phần tử. Ngoài ra, dãy \(A\) là một dãy không giảm (\(A_i \le A_{i+1}\) \(\forall\) \(1 \leq i < n\)). Trong một thao tác, các bạn có thể xoá một phần tử ở \(B\) và chèn nó vào một vị trí bất kì trong \(A\). Rõ ràng, các bạn không thể thực hiện thao tác trên quá \(m\) lần.

Hãy tìm cách thực hiện thao tác trên một cách tối ưu để \(A\) vẫn là một dãy tăng dần và độ dài của \(A\) là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) lần lượt là số phần tử của dãy \(A\) và \(B\).

• Dòng tiếp theo chứa \(n\) số nguyên dương \(A_i\) biểu thị một phần tử của dãy \(A\).

• Dòng cuối cùng chứa \(m\) số nguyên dương \(B_i\) biểu thị một phần tử của dãy \(B\).

Output

• Hãy in ra độ dài lớn nhất của dãy \(A\) sau khi thực hiện thao tác một cách tối ưu.

Scoring

• Trong toàn bộ dữ liệu có \(1 \leq a_i \leq 10^9\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 10\).

• \(50\)% điểm tương ứng với \(1 \leq n, m \leq 2*10^5\).

Example

3 2
1 2 3
1 4

4

2 2
1 5
4 3

4

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L<R\leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên bằng phần tử cuối cùng (\(A_L=A_R\)).
• Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu: Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.

Constraints

• \(N\leq 10^5\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
• Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
• Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)

Example

7
3 3 3 3 1 11 1

13

Những viên đá sắc màu

Có tất cả \(n\) hòn đá trên bàn, \(n\) viên đấy có màu và có thể là R (đỏ), B (xanh lam), G (xanh lục). Bạn biết được màu của \(n\) viên đá trên bàn, hãy tìm số đá ít nhất phải lấy ra sao cho không có hai viên đá cạnh nhau trên bàn mà lại giống nhau.

Input

• Dòng thứ nhất nhập số \(n\text{ }(1\leq n\leq 100)\)
• Dòng thứ hai là màu sắc của \(n\) viên đá, là một xâu gồm các kí tự R, G, B.

Output

• Một dòng kết quả bài toán

Example

3 
RRG

1

5
RRRRR

4

Hãy đếm số cách mà các số \(1, 2,\ldots,n\) có thể được chia thành hai tập hợp có tổng bằng nhau.

Ví dụ, với \(n = 7\), có \(4\) cách chia:

• \(\{1,3,4,6\}\) và \(\{2,5,7\}\)
• \(\{1,2,5,6\}\) và \(\{3,4,7\}\)
• \(\{1,2,4,7\}\) và \(\{3,5,6\}\)
• \(\{1,6,7\}\) và \(\{2,3,4,5\}\)

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) \((1 \leq n \leq 500)\).

Output

• In đáp án - số cách thoả mãn chia lấy dư cho \(10^9 + 7\).

Example

7

4

Khoảng cách chỉnh sửa giữa hai xâu là số lượng thao tác tối thiểu cần thiết để chuyển đổi một xâu thành xâu kia.

Các thao tác được phép là:

• Thêm một ký tự vào xâu
• Xóa một ký tự khỏi xâu
• Thay thế một ký tự trong xâu

Ví dụ: khoảng cách chỉnh sửa giữa LOVE và MOVIE là \(2\), vì trước tiên bạn có thể thay thế L bằng M, sau đó thêm I.

Nhiệm vụ của bạn là tính toán khoảng cách chỉnh sửa giữa hai xâu.

Input

• Dòng đầu tiên có một xâu chứa \(n\) ký tự trong khoảng từ A–Z
• Dòng thứ hai có một xâu chứa các ký tự \(m\) trong khoảng từ A–Z

Constraints

• \(1 \leq n \leq 5000\)

Output

• In một số nguyên: khoảng cách chỉnh sửa giữa các xâu

Example

LOVE
MOVIE

2

Với một hình chữ nhật \(a \times b\), nhiệm vụ của bạn là cắt nó thành các hình vuông. Trong mỗi bước, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho độ dài các cạnh vẫn là số nguyên. Số bước tối thiểu là bao nhiêu?

Input

• Gồm một dòng duy nhất chứa hai số nguyên \(a\) và \(b\).

Output

• In một số nguyên: số lần di chuyển tối thiểu.

Constraints

• \(1 \leq a, b \leq 500\)

Example

3 5

3

Bình và An là đôi bạn thân. Hàng ngày, hai bạn cùng nhau đi bộ tới trường. Trên con đường mà hai bạn đi có một hàng cây gồm \(n\) cây, các cây được đánh thứ tự từ \(1\) đến \(n\). Bình và An rất yêu thích hàng cây này, hai bạn đã tìm hiểu và biết được độ cao của từng cây, cây thứ \(k \ (k=1,2,…,n)\) có độ cao là \(h_k\). Thật đặc biệt, các cây có độ cao đôi một khác nhau. Một hôm, An đố Bình bài toán sau: Tìm hai số \(i,j\) là chỉ số của hai cây thỏa mãn điều kiện: \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất. Bình đề nghị: “Chúng ta hãy cùng lập trình giải quyết bài toán này.”

Yêu cầu: Cho \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n\) là độ cao của \(n\) cây, hãy tìm hai số \(i,j\) là chỉ số của hai cây mà \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất.

Input

• Dòng đầu chứa một số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n \ (h_i \leq 10^6).\)

Output

• Một dòng chứa một số là giá trị \((j-i)\) lớn nhất tìm được. Nếu không tồn tại hai chỉ số \(i,j\) thỏa mãn thì in ra \(-1\).

Scoring

• Subtask #1 (\(50\%\) số điểm): \(n \leq 10^3\).
• Subtask #2 (\(50\%\) số điểm): \(n \leq 10^5\).

Example

4
4 2 1 3 

2

3
4 2 1 

-1

Có một lưới ô vuông có kích thước \(N × N\) được đánh chỉ số hàng từ \(1\) đến \(N\) (theo chiều từ trên xuống dưới) và chỉ số cột từ \(1\) đến \(N\) (theo chiều từ trái sang phải). Mỗi ô trong lưới được xác định vị trí bởi một cặp số \((i; j)\) trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột.

Tại ô \((1; 1)\) người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.

Yêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô \((1; 1)\) đến ô \((N; N)\). Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.

VD: Xét lưới ô vuông kích thước \(3\times 3\) như hình vẽ sau:

Trong lưới ô vuông \(3\times 3\) này người ta đặt viên đá vào ô \((1;3)\) và ô \((2;1)\).
Với dữ kiện trên thì robot có tất cả 2 đường đi như sau:

\((1;1) → (1;2) → (2;2) → (2;3) → (3;3)\)

\((1;1) → (1;2) → (2;2) → (3;2) → (3;3)\)

Input

Đọc từ file văn bản ROBOT.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(M\) (mỗi số cách nhau 1 dấu cách; \(M < N\)).
• \(M\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương \(i\) và \(j\) (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.

Output

• Ghi ra file văn bản ROBOT.OUT một số \(k\) là số đường đi của robot từ ô \((1; 1)\) đến ô \((N; N)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(10 < N \le 30\).
• Subtask \(3\) (\(30\%\) số điểm): \(30 < N \le 100\).

Example

3 2
1 3
2 1

2

Cho trước một mảng độ dài \(n\) trong đó có một số vị trí chưa được xác định giá trị. Hãy đếm số cách điền giá trị vào những vị trí đó thoả mãn điều kiện sau:

• Các giá trị trong mảng là số nguyên trong khoảng từ \(1\) đến \(m\)
• Chênh lệch giữa hai phần tử liền kề không quá \(1\)

Input

• Dòng đầu tiên có hai số nguyên \(n\) và \(m\): kích thước mảng và giới hạn trên cho mỗi giá trị
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng. Giá trị \(0\) biểu thị một giá trị không xác định

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 100\)
• \(0 \leq x_i \leq m\)

Output

• In một số nguyên: số lượng dãy (cũng là số lượng cách điền) chia lấy dư cho \(10^9 + 7\)

Example

3 5
2 0 2

3

Có \(n\) dự án bạn có thể tham gia. Đối với mỗi dự án, bạn biết ngày bắt đầu và ngày kết thúc của nó và số tiền bạn sẽ nhận được làm phần thưởng. Bạn chỉ có thể tham dự một dự án trong một ngày.

Số tiền tối đa mà bạn có thể kiếm được là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng dự án.
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\) và \(p_i\): ngày bắt đầu, ngày kết thúc và phần thưởng.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a_i \leq b_i \leq 10^9\)
• \(1 \leq p_i \leq 10^9\)

Output

• In một số nguyên: số tiền tối đa mà bạn có thể kiếm được.

Example

4
2 4 4
3 6 6
6 8 2
5 7 3

7

Lương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muốn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.

Input

• Dòng đầu có 2 số nguyên \(n, k\).

• Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\)

Output

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

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).

Example

6 3
1 4 3 7 11 9 

3

6 2
1 4 3 7 11 9

2

 6 1
1 4 3 7 11 9

1

Năm nay, cuộc thi chọn học sinh giỏi Duyên Hải có một nhà tài trợ trao một phần thưởng vô cùng thú vị cho thí sinh giành giải nhất môn Tin học. Số tiền thưởng mà thí sinh nhận được chính là số điểm mà thí sinh đó lấy được trong trò chơi mà nhà tài trợ đưa ra:

Cho một dãy \(n\) số nguyên (\(a_1, a_2, …, a_n\)). Người chơi có thể thực hiện những thao tác sau đây trên dãy đã cho:

• Chọn một số \(a_i\) bất kỳ thì nhận được số điểm là \(a_i\) (\(i = 1÷n\)).
• Đồng thời cũng phải xóa đi tất cả các số có giá trị là (\(a_i – 1\)) và (\(a_i + 1\)) có trong dãy ngay sau đó.

Yêu cầu: Ban đầu người chơi có 0 điểm. Bạn hãy cho biết số tiền lớn nhất mà thí sinh giải nhất có thể nhận được từ nhà tài trợ.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1\le n \le 20000\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, …, a_n\) (\(1\le a_i \le10000\)), mỗi số cách nhau một dấu cách.

Output

• Đưa ra một số nguyên là số tiền lớn nhất mà thí sinh giải nhất có thể nhận được.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \le n \le 1000\), \(1\le a_i \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(1\le n \le 20000\), \(1\le a_i \le 10000\).

Example

3
3 4 2

6

6
2 2 3 3 3 4

9