Cho một tam giác số gồm n hàng. Mỗi phần tử trong hàng (trừ hàng cuối) có thể đi xuống hàng kế tiếp, theo một trong hai hướng:

Từ trên xuống (cùng chỉ số cột j), hoặc

Từ trên bên trái xuống (chỉ số cột j - 1).

Hãy tìm tổng lớn nhất có thể đạt được khi đi từ đỉnh tam giác xuống đáy.

Dữ liệu vào (Input)

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 100).

Tiếp theo là n dòng, dòng thứ i chứa i số nguyên là các phần tử của hàng thứ i. (Các số có giá trị tuyệt đối ≤ 10⁴)

Dữ liệu ra (Output)

In ra một số nguyên — là tổng lớn nhất có thể đạt được.

Ví dụ 1

Input

4
2
4 1
1 2 7
8 3 9 6

Output

19

Giải thích:

Đường đi lớn nhất là: 2 → 4 → 2 → 9 = 19

Cho một ma trận gồm n hàng và m cột, mỗi ô có một giá trị biểu thị chi phí đi qua ô đó.

Bạn bắt đầu tại ô (0, 0) (góc trên bên trái) và muốn đi đến ô (n-1, m-1) (góc dưới bên phải).

Tại mỗi bước, bạn chỉ được phép đi sang phải hoặc đi xuống dưới.

Hãy tìm tổng chi phí nhỏ nhất để đi từ ô (0, 0) đến ô (n-1, m-1).

Dữ liệu vào (Input)

Dòng đầu chứa hai số nguyên n, m (1 ≤ n, m ≤ 100).

Tiếp theo là n dòng, mỗi dòng chứa m số nguyên (|cost[i][j]| ≤ 10⁴) — là chi phí của từng ô.

Dữ liệu ra (Output)

In ra một số nguyên duy nhất — là tổng chi phí nhỏ nhất.

Ví dụ:

Input

3 3
1 3 1
1 5 1
4 2 1

Output

7

Giải thích:

Đường đi tối ưu: 1 → 3 → 1 → 1 → 1 (Tổng = 7)

Trong nhân dịp đạt được 100 triệu subscribers của HCN , HCN đã chọn ra subscriber thứ 100 triệu của mình và mời người đó tham gia trò chơi chọn quà. Rất may mắn là bạn chính là subscriber thứ 100 triệu của HCN!

Sau khi gặp gỡ và trò chuyện với HCN, bạn được HCN phổ biến về trò chơi. Nội dung của trò chơi như sau: Có n phần quà trên bàn, mỗi phần quà có giá trị ai (1 ≤ i ≤ n). Bạn sẽ được thực hiện thao tác chọn quà như sau nhiều lần: Đầu tiên, bạn chọn một phần quà bất kỳ trên bàn, giả sử nó có giá trị là x. Khi đó, tất cả những phần quà có giá trị là x - 1 và x + 1 sẽ bị lấy ra khỏi bàn. Trò chơi kết thúc khi bạn không thể thực hiện thao tác chọn quà bất cứ một lần nào nữa và bạn sẽ được mang về tất cả những phần quà còn lại trên bàn.

Hãy tối ưu cách chơi của bạn để tổng giá trị của các phần quà bạn mang về là lớn nhất.

Input:

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^5);

• Dòng tiếp theo chứa n số nguyên ai (1 ≤ ai ≤ 10^5, 1 ≤ i ≤ n).

Output: In ra kết quả là tổng giá trị phần quà lớn nhất mà bạn có thể mang về được trong trò chơi.

Input:

3
1 3 2

Output:

4

Giải thích: Cách chọn quà tối ưu như sau:

• Chọn phần quà có giá trị là 1 → Các phần quà có giá trị là 2 bị bỏ ra khỏi bàn.

• Chọn phần quà có giá trị là 3.

Khi đó, tổng giá trị các phần quà bạn có thể mang về là: 1 + 3 = 4.

Input:

5
4 1 1 2 3

Output:

6

Giải thích: Cách chọn quà tối ưu như sau:

Chọn phần qua có giá trị là 2 → Các phân quà có giá trị la 1 và 3 bị bỏ ra khỏi bàn, chọn phần quà có giá tri là 4. Khi đó, tổng giá trị các phần quà bạn có thể mang về là: 4 + 2 = 6.

Input:

5
6 6 6 6 6

Output:

30

Giải thích: Bạn có thể lấy cả 5 phần quà trên bàn mà không phải bỏ phần quà nào.

Đề bài rất đơn giản, bạn hãy tính N! chia dư cho (10^9 + 7).

Đầu vào:

Dòng 1 là số bộ test T

T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0<=N<=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
1
2
3
4
5

Output:

1
2
6
24
120

Cho dãy số Tribonacci với F[0] = 0, F[1] = 0, F[2] = 1, F[n) = F[n - 1] + F[n - 2] + F[n - 3] với n >= 3. Hãy tính F[n] chia dư cho 10^9 + 7.

--

Đầu vào:

Dòng 1 là số bộ test T

T dòng tiếp theo mỗi dòng là một giá trị cần tính

Ràng buộc:

1<=T<=10000

1<=N<=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
2
4
6
8
10

Output:

1
2
7
24
81

Cho 2 số nguyên L, R, hãy đếm xem trong đoạn từ L tới R có bao nhiêu số nguyên tố.

Đầu vào:

• Đòng 1 là số bộ test T

• T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0＜＝N＜=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
3 19
4 65
4 44
1 17
1 7

Output:

7
16
12
7
4

Cho số nguyên dương N, hãy tính tích các số nguyên tố trong đoạn từ 0 đến N.

Đầu vào:

Dòng 1 là số bộ test T

T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0<=N<=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng, vì kết quả quá lớn nên hãy chia dư cho 10^9 + 7.

Input:

5
20
16
10
22
29

Output:

9699690
30030
210
9699690
469693188

Cho mảng A[] gồm N số nguyên. Nhiệm vụ của bạn là sắp xếp lại mảng số với số lượng bước là ít nhất. Tại mỗi bước, bạn chỉ được phép chèn phần tử bất kỳ của mảng vào vị trí bất kỳ trong mảng. Ví dụ A[] = (2, 3, 5, 1, 4, 7, 6 ) sẽ cho ta số phép chèn ít nhất là 3 bằng cách lấy số 1 chèn trước số 2, lấy số 4 chèn trước số 5, lấy số 6 chèn trước số 7 ta nhận được mảng được sắp.

Đầu vào: Dòng đầu tiên là N; Dòng thứ 2 gồm N phần tử của màng A;

Ràng buộc: 1<=N<=1000; 1<=A[i]<=1000

Đầu ra: Đưa ra kết quả trên 1 dòng.

Input 01:

8
2 12 3 15 3 16 12 4

Output 01:

4

Input 02:

13
143 340 571 845 211 228 274 443 666 594 491 814 24

Output 02:

6

Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là tính tổng lớn nhất của dãy con trong mảng với một điều kiện đó là trong dãy con này không được có 2 phần tử năm liền kề nhau.

Đầu vào: Dòng đầu tiên là N là số lượng phần tử trong mảng: Dòng thứ 2 là A[i]

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

Đầu ra: In ra kết quả của bài toán

Input:

7
1 1 1 4 1 1 100

Output:

105

Input:

7
314 514 148 451 896 589 296

Output:

1706

Một chiếc cầu thang có N bậc. Mỗi bước, bạn được phép bước lên trên tối đa K bước. Hỏi có tất cả bao nhiều cách bước để đi hết cầu thang? (Tổng số bước đúng bằng N).

Đầu vào: Dòng duy nhất chứa 2 số nguyên N và K

Ràng buộc: 1<=N<=100000; 1<=K＜=100

Đầu ra: In ra đáp án tìm được trên một dòng theo modulo 10^9+7.

Input:

4 2

Output:

5

Input:

7 3

Output:

44

Cho số nguyên dương N, hãy đếm xem trong đoạn từ 0 tới N có bao nhiêu số nguyên tố.

Hướng dẫn:

• Bước 1 : Sàng số nguyên tố

• Bước 2: Gọi F[i] là số lượng các số nguyên tố từ 0 tới i, xây dựng mảng F[i] sau khi sàng

Đầu vào:

• Đòng 1 là số bộ test T

• T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0＜＝N＜=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
2
4
6
8
10

Output:

1
2
3
4
4

Một con ếch có thể nhảy 1, 2, 3 bước để có thể lên đến một đỉnh cần đến. Hãy đếm số các cách con ếch có thể nhảy đến đỉnh.

Đầu vào: Số nguyên dương N mô tả số bước con ếch cần di chuyển để nhảy tới đỉnh

Ràng buộc: 1<=N<=40

Đầu ra: In ra kết quả của bài toán

Input:

5

Output:

13

Cho ma trận A các số nguyên có N hàng và M cột. Tim đường đi từ ở [1, 1] tới Ô [N, M] sao cho tổng các số trên đường đi là lớn nhất có thể, biết rằng ở mỗi bước chi có thể đi từ ô hiện tại xuống ô phía dưới hoặc đi sang phải.

Đầu vào: Dòng đầu tiên N và M; N dòng tiếp theo mỗi dòng gồm M phần tử.

Ràng buộc: 1 <= N, M <= 100: 1 <= A[i][j] <= 10^9

Đầu ra: In ra đường đi có tổng lớn nhất.

Input:

3 3
1 2 2
3 10 2
5 7 2

Output:

23

Cho mảng 2 chiều A gồm N hàng và N cột, hãy tim 1 đường đi từ dòng 1 tới dòng N sao cho các phần tử trên đường đi đó là lớn nhất có thế. Biết rằng ở mỗi bước đi từ ô hiện tại chỉ có thế đi xuống ô dưới bên trái, ô dưới bên phải hoặc ô dưới của ô hiện tại. Hây tìm 1 đường đi có tổng các số trên đường đi là lớn nhất

Đầu vào:

Dòng 1 là N

N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc: 1 <= N <= 100; 1 <= A(i][j] <= 100

Đầu ra: In ra kết quả của bài toán

Input:

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

Output:

33