Có N cái que, mỗi cái có một trong ba màu xanh dương, xanh lá cây và màu đỏ.

Yêu cầu: Cho biết màu và độ dài của mỗi cái que, hỏi có bao nhiêu tam giác được tạo ra từ N cái que đã cho mà mỗi tam giác có các cạnh đủ cả ba màu?

Dữ liệu vào: gồm:

• Dòng đầu tiên chứa số nguyên dương N (N ≥ 3);
• N dòng tiếp theo, mỗi dòng chứa hai giá trị, một chữ cái c và một số nguyên dương l là màu và độ dài của một cái que ghi cách nhau dấu cách (c ∈ {'b','g','r'}, b-xanh dương, g - xanh lá cây, r - đỏ; ~1 ≤ l ≤ 10^5~).

Kết quả: ghi ra một dòng ghi một số nguyên dương là số tam giác có thể tạo được.

Ràng buộc:

• 30% số tests tương ứng với 30% số điểm của bài có: N ≤ 100;
• 20% số tests khác tương ứng với 20% số điểm của bài có: N ≤ 1500;
• 30% số tests khác tương ứng với 30% số điểm của bài có: N ≤ 7500;
• 20% số tests còn lại tương ứng với 20% số điểm của bài có: N ≤ 10000.

Ví dụ:

Input

5
r 10
g 10
b 12
r 5
g 6

Output

3

Giải thích: Ba tam giác: {(r 10), (g 10), (b 12)}; {(r 10), (g 6), (b 12)}; {(r 5), (g 10), (b 12)}.

Nguồn

Bạn An đại diện lớp 11 Tin tổ chức trò chơi tìm mật mã như sau: Cho một số nguyên dương x, mật mã của x chính là số lượng ước của x. Vi dụ: x = 8 có bốn ước 1,2, 4, 8 nên mật mã của x là 4.

Trong quá trình tham gia trò chơi thấy bài toán bạn An đưa ra còn đơn giản quá nên bạn Sơn mở rộng bài toán như sau: Cho n số nguyên dương a1, a2,..., an.

Gọi ~S = a_1 × a_2 × … × a_n~ yêu cầu tìm mật mã của S.

Ví dụ: với dãy số { 2, 8, 4}, S = 64 có bảy ước 1, 2, 4, 8, 16, 32, 64. Vậy mật mã của dãy là 7.

Yêu cầu: Cho dãy số ~a_1, a_2, ..., a_n~, hãy tìm mật mã của dãy số đã cho.

Dữ liệu vào gồm:

• Dòng đầu tiên chứa số nguyên dương n ~(1 ≤ n ≤ 10^6)~,
• Dòng thứ hai chứa n số nguyên ~a_1, a_2,..., a_n~ ~(2 ≤ a_i ≤ 10^6)~ các số ghi cách nhau dấu cách.

Kết quả: ghi ra một số là mật mã tìm được, tương ứng với số lượng ước của dãy khi chia lấy phần dư cho ~10^9+7~.

Ràng buộc:

• 30% số tests tương ứng với 30% số điểm của bài có: ~S ≤ 10^{12}~;
• 20% số tests khác tương ứng với 20% số điểm của bài có: n ≤ 1000 và ~a_i~ là số nguyên tố;
• 50% số tests còn lại tương ứng với 50% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Input

3
2 8 4

Output

7

Nguồn

Cô giáo cần tính toán kế hoạch đưa M học sinh trở về trường sau một chuyến tham quan dã ngoại. Các học sinh được đánh số từ 1 đến M. Trường và các địa điểm tham quan đều nằm trên một trục đường giao thông. Hiện tại, tính từ trường thì học sinh thứ i tham quan tại địa điểm cách trường ~x_i~ km. Tất cả các ~x_i~ đều là số nguyên không âm và ~x_1 ≤ x_2 ≤ x_{M-1} ≤ x_M~ . Mỗi học sinh phải đi thẳng về trường, họ có thể đi bộ hoặc đi bằng xe buýt. Khi đi bộ thì học sinh thứ i cần ~v_i~ đồng để uống nước hoặc dùng cho các chi phí cần thiết khác.

Có N xe buýt, được đánh số từ 1 đến N. Xe thứ j chờ khách tại địa điểm cách trường ~y_j~ km và khi được thuê để về trường cần phải trả ~c_j~ đồng. Tất cả các ~y_j~ đều là số nguyên không âm và ~y_1 ≤ y_2 ≤ ...≤ y_{N-1} ≤ y_N~. Có thể có nhiều học sinh cùng lên một chuyến xe nếu họ đang ở tại địa điểm chờ khách của xe đó. Mỗi chuyến xe được thuê, dù chỉ có một người đi hay nhiều người cùng đi thì tiền thuê xe cũng không thay đổi. Mỗi xe được thuê sẽ chạy thẳng từ địa điểm chờ về trường, không dừng lại đón các học sinh khác tại bất kỳ một địa điểm nào trên đường.

Yêu cầu: Hãy giúp cô giáo tính toán tổng số tiền ít nhất để đưa học sinh về trường, cụ thể hơn giúp cô tính tổng số tiền ít nhất để đưa một học sinh đầu tiên, hai học sinh đầu tiên,... cuối cùng là M học sinh về trường.

Dữ liệu vào: gồm:

• Dòng đầu tiên chứa số nguyên dương N (N ≥ 1);
• N dòng tiếp theo, dòng thứ j chứa hai số nguyên dương ~y_j~, ~c_j~ cách nhau dấu cách;
• Dòng tiếp theo chứa số nguyên dương M (M ≥ 1);
• M dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ~x_i~, ~v_i~ cách nhau dấu cách. (~0 ≤ x_i , y_j ≤ 2^{30}~; ~x_i ≤ x_{i+1}~, với mọi i: 1 ≤ i < N; ~y_j ≤ y_{j+1}~, với mọi j: 1 ≤ j < M; ~1 ≤ v_i ≤ 2^{30}~, ~1 ≤ c_j ≤ 2^{40}~)

Kết quả: ghi ra M số nguyên dương, các số cách nhau dấu cách, số thứ k là tổng số tiền ít nhất để đưa k học sinh đầu tiên về trường.

Ràng buộc:

• 10% số tests tương ứng với 10% số điểm của bài có: N ≤ 10, M ≤ 6;
• 20% số tests khác tương ứng với 20% số điểm của bài có: N ≤ 14, M ≤ ~10^2~
• 40% số tests khác tương ứng với 40% số điểm của bài có: N ≤ ~10^3~, M ≤ ~10^2~
• 30% số tests còn lại tương ứng với 30% số điểm của bài có: N ≤ ~2 × 10^4~, M ≤ ~10^3~.

Ví dụ:

Input

6
1 3
2 10
3 100
4 100
5 15
6 10
3
2 5
4 9
8 3

Output

8 28 44

Giải thích ví dụ:

Kế hoạch đi và chi phí nhỏ nhất:

• Với học sinh đầu tiên, học sinh 1 đi bộ đến địa điểm chờ của xe số hiệu 1, sau đó đi xe số hiệu 1 về trường, chi phí: (2 - 1) x 5 + 3 = 8.
• Với hai học sinh đầu tiên, học sinh 2 đi bộ đến địa điểm xe số hiệu 2, sau đó hai người cùng đi trên một chuyến xe số hiệu 2 về trường, chi phí: (2 - 2) x 5 + (4-2) x 9 + 10 = 28.
• Với ba học sinh, học sinh 2 đi bộ đến địa điểm xe số hiệu 2, sau đó cả hai người đi xe số hiệu 2 về trường, chi phí 28. Còn học sinh 3 đi bộ đến địa điểm xe số hiệu 6, sau đó đi xe số hiệu 6 về trường, chi phí: (8 - 6) x 3 + 10 = 16. Chi phí cả ba học sinh là: 28 +16 = 44.

Nguồn