Trong một cuộc thi Tin học trẻ sáng tạo, ban tổ chức đưa ra một trò chơi liên quan đến các con số tự nhiên, trò chơi được phát biểu như sau. Một số nguyên dương được gọi là số nguyên tố đặc biệt nếu nó thỏa mãn đồng thời các điều kiện sau:

Là số nguyên tố. 
Tổng các chữ số của nó cũng là số nguyên tố. 
Số thu được khi đảo ngược các chữ số cũng là số nguyên tố.

Yêu cầu: Cho hai số nguyên dương L, R. Hãy đếm có bao nhiêu số trong đoạn [L, R] là số nguyên tố đặc biệt.

Ví dụ:

• Số 131 là số nguyên tố.
• Tổng các chữ số của 131: 1+3+1=5 là số nguyên tố.
• Đảo ngược số 131 thì ra 131 là số nguyên tố => Số 131 là hợp lệ.

Dữ liệu vào: Một dòng gồm hai số nguyên L, R (1 ≤ L ≤ R ≤ 10^5)

Dữ liệu ra: In ra một số nguyên là số lượng số thỏa mãn yêu cầu đề bài.

Ghi chú: Khi đảo số, các chữ số 0 ở đầu sẽ bị loại bỏ.

Ví dụ:

Input:

50 200

Output:

8

Để chuẩn bị cho một chuyến dã ngoại, bạn An cần mang theo một số vật dụng cần thiết. Tuy nhiên, chiếc balo của An chỉ có thể chịu được tối đa W kilogam, nên An phải lựa chọn các món đồ một cách hợp lý. Để giải quyết vấn đề cùa bạn An thì ta có *N *món đồ, mỗi món đồ thứ i có:

• Khối lượng là Wi (kg).
• Giá trị sử dụng là Vi (điểm).

Không giống như những lần trước, lần này An có yêu cầu đặc biệt: An phải chọn đúng K món đồ để mang theo.

Yêu cầu: Hãy giúp An chọn ra đúng K món đồ sao cho:

• Tổng khối lượng không vượt quá W.
• Tổng giá trị sử dụng là lớn nhất có thể.

Nếu không tồn tại cách chọn thỏa mãn, hãy in ra 0.

Dữ liệu vào:

• Dòng đầu tiên: Gồm ba số nguyên N, W, K (1≤ N ≤100; 1≤ W ≤1000; 1≤ K ≤ N).
• N dòng tiếp theo, mỗi dòng gồm hai số nguyên Wi, Vi (1≤ Wi ≤ W; 1≤ Vi ≤1000)

Dữ liệu ra: In ra một số nguyên:

• Giá trị lớn nhất đạt được.
• Hoặc 0 nếu không thể chọn đúng K món.

Ví dụ:

Input:

4 7 2

1 1

3 4

4 5

5 7

Output:

9

Một công ty thiết kế xây dựng đang lưu trữ các file bản vẽ lớn. Họ cho dãy A gồm N số nguyên dương, mỗi phần tử là một số biểu diễn dung lượng của một file bản vẽ. Hãy chia dãy thành đúng K đoạn liên tiếp (mỗi đoạn không rỗng) sao cho:

• Mỗi đoạn chứa các phần tử (file) liên tiếp.
• Giá trị lớn nhất của tổng các phần tử (file) trong mỗi đoạn là nhỏ nhất có thể.

Yêu cầu: Tìm giá trị nhỏ nhất của tổng lớn nhất trong các đoạn sau khi chia.

Dữ liệu vào:

• Dòng 1: Cho hai số nguyên N, K (1 ≤ K ≤ N ≤ 105)
• Dòng 2: N số nguyên Ai (1 ≤ Ai ≤ 109)

Dữ liệu ra: In ra một số nguyên là kết quả theo yêu cầu của đề bài.

Ví dụ:

Input:

5 2

7 2 5 10 8

Output:

18

Giải thích: Chia: [7 2 5] và [10 8]; Max = 14 vs 18 → chọn 18 là nhỏ nhất có thể.

Một thành phố đang triển khai hệ thống giao thông thông minh. Một số tuyến đường được đánh dấu là đường ưu tiên (VIP). Một xe cứu thương cần đi từ nút 1 đến nút N, nhưng do quy định, xe chỉ được đi qua tối đa K tuyến VIP đó (đường đi ở dạng vô hướng).

Yêu cầu: Tìm quãng đường ngắn nhất từ 1 đến N sao cho số tuyến VIP sử dụng không vượt quá K. Nếu không tồn tại đường đi thỏa mãn, in ra -1.

Dữ liệu vào: Cho tệp Input.txt với dữ liệu đầu vào mẫu đã cho bên dưới. - Dòng 1: Ba số nguyên N, M, K (1 ≤ N ≤ 105, 1≤ M ≤ 2 x 105, 0 ≤ K ≤ 20, 1 ≤ W ≤ 109) - M dòng tiếp theo, mỗi dòng gồm 4 số nguyên U, V, W, T (U, V: hai đỉnh của cạnh; W: trọng số cạnh; T = 1 nếu là cạnh VIP, T = 0 nếu là cạnh thường.

Dữ liệu ra: Ghi kết quả ra tệp Output.txt là độ dài đường đi ngắn nhất thỏa mãn yêu cầu. Nếu không tồn tại, in ra -1.

Ví dụ:

Input 1:

4 5 1 1 2 5 0 2 3 5 1 1 3 15 0 3 4 5 0 2 4 20 0

Output 1:

15

Input 2:

3 2 0 1 2 1 1 2 3 1 1

Output 2:

-1

Giải thích test 01: Các đường đi:

1 → 2 → 3 → 4

Trọng số: 5 + 5 + 5 = 15 VIP: 1 cạnh (2→3)

1 → 3 → 4

Trọng số: 15 + 5 = 20 VIP: 0

1 → 2 → 4

Trọng số: 5 + 20 = 25