Một số được gọi là số tăng giảm nếu số đó có các chữ số thỏa mãn hoặc tăng dần, hoặc giảm dần từ trái qua phải.

Hãy đếm các số nguyên tố là số tăng giảm với số chữ số cho trước

INPUT

2

OUTPUT

21

Giới hạn thời gian: 1 giây Giới hạn bộ nhớ: 256 MB Dữ liệu vào: Số nguyên dương N (số chữ số) nằm trong khoảng từ 1 đến 9.

Phân bố điểm chi tiết:

Subtask 1 (chiếm 30% số điểm): N nằm trong khoảng từ 1 đến 4. Gợi ý: Số lượng số phải kiểm tra rất ít, dễ dàng thực hiện duyệt.

Subtask 2 (chiếm 30% số điểm): N nằm trong khoảng từ 5 đến 7. Gợi ý: Yêu cầu áp dụng phương pháp sinh số (quay lui/đệ quy) thay vì duyệt trâu, và kiểm tra hiệu quả tính nguyên tố.

Subtask 3 (chiếm 40% số điểm): N bằng 8 hoặc 9. Gợi ý: Giới hạn này thử nghiệm khả năng xử lý số lớn (long long) và đệ quy sâu để sinh tất cả các số tăng giảm có thể.

Một số N được coi là đẹp nếu nếu nó có tính chất thuận nghịch và tổng chữ số chia hết cho 10. Bài toán đặt ra là cho trước số chữ số N. Hãy đếm xem có bao nhiêu số đẹp với số chữ số như vậy.

INPUT:

2

OUTPUT:

1

Subtask 1 (chiếm 30% số điểm): N nằm trong khoảng từ 1 đến 6. Gợi ý: Với giới hạn này, thí sinh có thể sử dụng phương pháp duyệt toàn bộ (Brute Force) các số có N chữ số để kiểm tra.

Subtask 2 (chiếm 30% số điểm): N nằm trong khoảng từ 7 đến 18. Gợi ý: Kết quả tính toán vẫn nằm trong phạm vi của kiểu số nguyên 64-bit (long long trong C++), có thể tính toán bằng công thức toán học bình thường.

Subtask 3 (chiếm 40% số điểm): N lớn hơn 18 và nhỏ hơn hoặc bằng 100000. Gợi ý: Kết quả là một số rất lớn (có thể lên tới hàng trăm nghìn chữ số), vượt quá phạm vi lưu trữ của các kiểu số thông thường. Thí sinh cần tìm ra quy luật và in kết quả dưới dạng chuỗi ký tự (xử lý số lớn).

BÀI 4: (4.0 điểm)

Cho xâu S và xâu T. Hãy đếm xem xâu T xuất hiện bao nhiêu lần trong xâu S.

Dữ liệu: Xâu S ở dòng 1 (độ dài <= 10^5), xâu T ở dòng 2 (độ dài <= 100).

Kết quả: Số lần xuất hiện.

Ràng buộc: Xâu chỉ gồm chữ cái thường.

Ví dụ:

Ví dụ 1:

Input:

ababab 
ab

Output:

3

Ví dụ 2:

Input:

aaaaa 
aa

Output:

4

Bạn cần xử lý n công việc. Mỗi công việc có thời lượng và hạn chót; bạn sẽ xử lý các công việc theo một thứ tự nào đó, lần lượt từng công việc. Phần thưởng cho một công việc là d - f, trong đó d là hạn chót của công việc và f là thời điểm bạn hoàn thành công việc đó. (Thời điểm bắt đầu là 0, và bạn phải xử lý tất cả các công việc kể cả khi có công việc cho phần thưởng âm.)

Hỏi phần thưởng tối đa bạn có thể đạt được nếu chọn thứ tự xử lý tối ưu?

Input:

Dòng đầu: số nguyên n - số lượng công việc.

Tiếp theo có n dòng, mỗi dòng gồm hai số nguyên a và d - lần lượt là thời lượng và hạn chót của công việc.

Output:

In ra một số nguyên: phần thưởng tối đa.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~1 \le a,d \le 10^6~

Ví dụ :

Input:

3
6 10
8 15
5 12

Output:

2