Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~. Một dãy chỉ số ~1 \le i_1 < i_2 < \dots < i_k \le n~ mà ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~, khi đó ~a_{i_1} < a_{i_2} < \dots < a_{i_k}~ được gọi là một dãy con tăng của ~A~. Hãy tìm độ dài dãy con tăng dài nhất của ~A~.

Input

• Dòng đầu ghi số nguyên dương ~n~ ~(n \le 1000)~.
• Dòng hai ghi dãy số nguyên ~A~ ~(|A_i| \le 10^9)~.

Output

• Một số nguyên là độ dài dãy con tăng đơn điệu dài nhất.

Sample Input 1

6
1 2 5 4 6 2

Sample Output 1

4

Sample Input 2

10
1 2 3 4 9 10 5 6 7 8

Sample Output 2

8

Mời thành công Loli trong việc về nhà, ông già lại tiếp tục đánh đố Loli bằng một câu hỏi khác. Lần này liên quan tới số Fibonacci. Ông già cần Loli tìm ra số fibonacci thứ ~N~ khi chia dư cho ~1770136969~.

Số Fibonacci là dãy số mà phần tử này là tổng của hai phần tử trước đó. VD: ~0, 1, 1, 2, 3, 5, 8, 13, 21, \dots~

Input:

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

Output:

• Gồm một dòng duy nhất là kết quả của bài toán.

Sample Input 1

4

Sample Output 1

5

Sample Input 2

6

Sample Output 2

13

Yên Bái tổ chức hội chợ nông sản. Dọc đại lộ Nguyễn Thái Học, ban tổ chức đã xây dựng ~m~ gian hàng liền nhau đánh số lần lượt ~1, 2, \dots, m~. Tuy nhiên chỉ có ~n~ gian hàng trong số chúng được thuê. Gian hàng thứ ~i~ được thuê có số hiệu ~x_i~. Không có hai gian hàng được thuê có cùng số hiệu.

Để tiết kiệm chi phí, ban tổ chức chỉ che mưa cho những gian hàng được thuê bằng những tấm bạt. Một tấm bạt phủ được từ gian hàng số hiệu ~u~ đến gian hàng số hiệu ~v~ ~(u \le v)~ được coi là có kích thước ~v-u+1~. Giá của một tấm bạt kích thước ~w~ là ~C_w~. Chú ý rằng những tấm bạt kích thước lớn hơn không nhất thiết phải đắt hơn những tấm bạt kích thước nhỏ hơn.

Hãy giúp ban tổ chức tính số tiền ít nhất để có thể mua bạt che tất cả các gian hàng được thuê. Chú ý rằng trong phương án tối ưu các tấm bạt có thể phủ chồng lên nhau ở một số gian hàng.

Input:

• Vào từ file văn bản MARKET.INP:
• Dòng đầu ghi hai số nguyên dương ~n,\ m~ ~(1\le n\le5000,\ 1\le m\le10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1,\ x_2,\ldots,x_n\ \ (1\le x_i\le m,\ x_i\neq x_j\ \forall i\neq j)~.
• Dòng thứ ba chứa m số nguyên ~C_1,C_2,\ldots,C_m\ \ (1\le C_i\le10^6)~ là giá của những tấm bạt kích thước ~1, 2, \dots, m~.

Output:

• Ghi ra file văn bản MARKET.OUT một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Sample Input 1

6 12
1 2 11 8 4 12 
2 3 4 4 8 9 15 16 17 18 19 19

Sample Output 1

9

Giải thích

Sample Input 1

5
10 1 50 20 5

Sample Output 1

1150

Sample Input

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

Sample Output

4
3 4 5 6

Sample Input

123456781234
567812345678

Sample Output

56781234

Sample Input

6
2
6
5
1
7
3

Sample Output

21 4
2
3
5
6

HD sáng tạo ra một phương pháp nén dữ liệu mới như sau:

• Cho dãy ~N~ phần tử bằng ~1~.
• Sử dụng các chữ số từ ~1~ đến ~A~ để nén dãy phần tử ban đầu sao cho tổng các phần tử sau khi nén bằng ~N~.

Ví dụ: Với ~N = 5, A = 3~ ta có thể các cách nén như sau: ~(1,1,1,1,1)~ thành ~(1,2,1,1); (1,2,2); (2,1,2); (3; 2); \dots~.

Yêu cầu: Cho ~N~ và ~A~. Hãy đếm số cách nén khác nhau?

Input:

Vào từ file văn bản COMPRESS.INP:

• Một dòng duy nhất chứa ~2~ số nguyên ~N~ và ~A~ ~(1 ≤ A ≤ N ≤ 50)~.

Output:

Ghi ra file văn bản COMPRESS.OUT:

• Một số duy nhất là số cách nén khác nhau.

Ví dụ:

COMPRESS.INP

2 1

COMPRESS.OUT

1

Hai đội Bình Minh và Rạng Đông thi đấu. Mỗi khi một đội ghi điểm, các cầu thủ đội còn lại phải chống đẩy số lần đúng bằng số điểm hiện tại của đội đối phương. Ví dụ, lần đầu đội Bình Minh ghi ~7~ điểm, đội Rạng Đông chống đẩy ~7~ lần. Lần thứ hai ghi ~3~ điểm (được tổng ~10~ điểm), đội Rạng Đông phải chống đẩy ~10~ lần. Tương tự, đội Bình Minh ghi tiếp ~2~ điểm, đội Rạng Đông chống đẩy tiếp ~12~ lần. Tổng số lần chống đẩy trong trường hợp này là ~7+10+12=29~.

An là một thành viên ở đội Rạng Đông. An đếm được mình đã chống đẩy tất cả ~N~ lần. Hỏi số điểm tối đa đội Bình Minh đã ghi được là bao nhiêu?

Input:

Vào từ file văn bản "PUSHUPS.INP":

• Dòng đầu chứa hai số nguyên dương ~N,\ M\ (N\le5000,\ \ M\le10)~ với ~N~ - số lần An chống đẩy trong trận đấu, ~M~ – số cách ghi điểm mà đội Bình Minh có thể thực hiện.
• Dòng thứ hai chứa ~M~ số nguyên dương ~S_i\ (S_i\le20)~ là số điểm tương ứng mà đội Bình Minh có thể ghi theo ~M~ cách tương ứng. Mỗi cách ghi điểm có thể thực hiện nhiều lần.

Output:

Ghi ra file văn bản "PUSHUPS.OUT" một số nguyên duy nhất là số điểm tối đa mà đội Bình Minh đã ghi được. Ghi ra ~-1~ nếu không tìm ra cách ghi điểm thỏa mãn trong trường hợp An nhớ nhầm.

Sample Input 1

29 3
7 2 3

Sample Output 1

14

Giải thích

• Số điểm lần lượt ghi là ~3, 2, 2, 7~. Số lần chống đẩy ~3+5+7+14=29~.

Alice và Bob chơi trò bốc xu từ tháp được xây dựng bởi ~N~ đồng xu. Hai bạn chọn hai số nguyên dương khác nhau ~K~ và ~L~. Hai người lần lượt đi. Alice di trước. Mỗi người, khi đến lượt mình, được bốc khỏi tháp ~1~, ~K~ hoặc ~L~ xu. Ai bốc được đồng xu (hoặc các đồng xu) cuối cùng là thắng. Sau rất nhiều lần chơi, Alice nhận thấy rằng có những trường hợp mình chắc chắn thắng không phụ thuộc vào cách đi của Bob, ngược lại, có trường hợp dù đi thế nào Bob vẫn thắng. Trước ván chơi mới Alice nóng lòng muốn biết mình có thắng được hay không.

Yêu cầu: Cho ~N~, ~K~ và ~L~. Hãy xác định Alice hay Bob sẽ thắng.

Input:

Vào từ file văn bản "COINS.INP":

• Dòng đầu tiên chứa 3 số nguyên ~K~, ~L~ và ~m~, trong đó ~m~ – số ván chơi ~(1 < K < L < 10, 3 < m < 50)~,
• Dòng thứ 2 chứa ~m~ số nguyên ~N_1, N_2, \dots, N_m~, trong đó ~N_i~ – số xu trong tháp ở ván chơi thứ ~i\ (1 \le N_i \le 10^6,\ i \in [1;m])~.

Output:

Ghi ra file văn bản "COINS.OUT" xâu ~m~ ký tự, ký tự thứ ~i~ là 'A' nếu Alice thắng được và bằng 'B' nếu Bob thắng.

Sample Input 1

2 3 5
3 12 113 25717 88888

Sample Output 1

ABAAB

Có ~n~ khách hàng đang xếp hàng gửi tiền vào ngân hàng ~X~. Số tiền mà mỗi khách hàng muốn gửi lần lượt là ~a_1, a_2, \dots, a_n~. Với mỗi người gửi tiền, thư ký ngân hàng phải tốn thời gian là ~1~ phút để hoàn tất thủ tục hồ sơ. Các khách hàng rất bận và họ chỉ có thể chờ trong một khoảng thời gian nào đó mà thôi, sau khoảng thời gian đó họ sẽ đi và không gửi tiền nữa. Thời gian mà các khách hàng có thể chờ lần lượt là ~t_1, t_2, \dots, t_n~ (tính theo phút). Chủ ngân hàng rất là tham lam, ông ta luôn muốn làm sao để có được nhiều tiền gửi nhất. Bạn hãy giúp thư ký lựa chọn thứ tự gửi tiền của các khách hàng sao cho số tiền ngân hàng có được là nhiều nhất (có thể phải chấp nhận từ chối một số khách hàng để đạt được mục đích).

Input:

Vào từ file văn bản "BANK.INP":

• Dòng thứ nhất là số nguyên ~n\ (1 \le n \le 10^4)~.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~t_i\ (1 \le a_i \le 10^5,\ 0 \le t_i \le 1000)~.

Output:

Ghi ra file văn bản "BANK.OUT" một số nguyên xác định tổng số tiền nhiều nhất có thể thu được.

Sample Input 1

4
10 1
20 2
5 2
12 0

Sample Output 1

42

Sample Input 2

3
10 0
20 1
5 1

Sample Output 2

30

Subtasks

• 60% số test có ~n \le 20,\ 0 \le t_i \le 100~.
• 40% số test còn lại không có ràng buộc gì thêm.

Sau khi mua một nùi truyện segg về, Loli cần phải cất giữ chúng ở trong một kệ sách. Kệ sách nhà Loli có ~n~ vị trí để đựng sách, các vị trí được đánh số lần lượt từ ~1~ tới ~n~. Ban đầu sẽ không có sách trên kệ. Mỗi ngày, Loli sẽ thực hiện một số thay đổi trên kệ sách. Có ~4~ hành động Loli có thể làm:

• ~1\ x~: Đặt một cuốn sách vào vị trí thứ ~x~. Nếu đã có sách ở vị trí ~x~ từ trước, giữ nguyên.
• ~2\ x~: Lấy cuốn sách (nếu có) ở vị trí thứ ~x~ ra.
• ~3~: Đảo ngược trạng thái trên kệ. Những vị trí có sách sẽ được lấy ra, và những vị trí không có sách sẽ được thêm sách vào.
• ~4\ x~: Đưa kệ sách trở về quá khứ, trạng thái kệ sách y hệt như ngày thứ ~x~. Nếu ~x=0~, thì trạng thái sẽ là ban đầu – tức là khi chưa có sách.

Sau mỗi ngày Loli muốn biết có bao nhiêu sách trên kệ. Bạn hãy code giúp Loli nhé!

Input:

Lấy từ tệp SHELF.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n\ (1\le n\le4000)~ – số vị trí trong kệ sách.
• Dòng tiếp theo chứa số nguyên ~q\ (1\le q\le5\times10^5)~ – số ngày cần tính.
• ~q~ dòng cuối cùng chứa các hành động trong ~q~ ngày theo quy ước phía trên.

Output:

Ghi ra tệp SHELF.OUT:

• Gồm ~q~ dòng, mỗi dòng chứa một số thể hiện số sách trên kệ vào ngày đó.

Sample Input 1

4
4
1 1
3
2 4
4 0

Sample Output 1

1
3
2
0

Ràng buộc

• 30% số test có ~q\le10^3~.
• 30% số test có ~n\le150~.
• 40% số test không có ràng buộc gì thêm.