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