Là người ngây thơ trong sáng, thẳng thắn thật thà, dễ tin người và rất rất cute như GSPVH; việc trở thành mục tiêu của sự troll là vô cùng dễ hiểu. Nhất là các học sinh đang trên đỉnh cao của sự trẻ trâu, troll GSPVH là không thể thiếu trong các buổi học. Các bé dùng nhiều thủ đoạn lấy lòng, trẻ trâu và giả trân để đánh vào sự dễ tin người và chống xáng zỡ kùng kurk của GSPVH; khiến dù đang say sưa giảng bài, GSPVH vẫn phải căng mình chống đỡ.

Trong đợt tập huấn tại Hà Nội lần này, đội tuyển Bắc Ninh dưới sự chỉ đạo của trẻ trâu trường Bích Phương, lên kế hoạch troll GS bằng cách dùng đồ ăn thơm ngon dụ dỗ GSPVH. Trước giờ lên lớp, Bích Phương ra tiệm tạp hóa mua hết nửa tiệm bánh kẹo, sữa uống và các loại đồ ăn. Sau đó, cứ thi thoảng vài phút một lần, các bạn trong đội tuyển Bắc Ninh lại đặt đồ ăn do Bích Phương mua lên mặt bàn để nhem thêm GS và bảo rằng sẽ mời hay tặng GS ăn. GSPVH với bản tính rất thật thà tin người của mình, không chút nghi ngờ để đồ ăn tại bàn các bạn và tiếp tục bài giảng đang say sưa của mình. GS định ninh rằng giảng xong giữa giờ sẽ có đồ ăn ngon, nào ngờ bài giảng chưa hết thì đồ ăn đã không cánh mà bay, như thể dàn chuột nhắt nào đã nhanh chóng tha đi mất. Thực ra chẳng có chuột nhắt nào đâu, chỉ có tám con chuột rất to ngồi hai bàn đầu phía ngoài của mà thôi.

Để đối phó với thủ đoạn troll mới của các trẻ trâu viên, trong buổi học đặc biệt nhận ngày Bích Phương bước sang tuổi 16, GSPVH mang sẵn một chiếc túi to. Khi thấy các bé để rất nhiều đồ ăn trên bàn, GSPVH sẽ bắt ngờ ra thông báo kết thúc buổi học, bất kể khi đó GS đang chữa bài chưa xong hay cả lớp đang làm gì. Sau đó GSPVH thu gom những món ăn ngon nhất trên bàn khăn gói mang về, không cho chúng có cơ hội tiêu thụ tấn. Tuy nhiên, thời điểm kết thúc buổi học chỉ có một, vì vậy GSPVH nhờ các bạn tốt bụng cute viết hộ một chương trình xử lý các sự kiện, giúp GSPVH tìm ra thời điểm kết thúc buổi học thích hợp nhất.

Cụ thể, bạn đầu trên bàn không có món ăn hay gói bánh kẹo nào. Chiếc túi của GSPVH có thể chứa được tối đa \(k\) món ăn. Các sự kiện trong buổi học thuộc một trong hai dạng sau:

• show t c: Một bạn đặt lên bàn một gói đồ ăn có độ hấp dẫn là \(t\) và cung cấp lượng dinh dưỡng là \(c\) calories.
• eat: Các bạn đội tuyển Bắc Ninh cảm thấy quá đói và thèm ăn, quyết định bốc ra và chia nhau món ăn nhiều calories nhất có trên bàn.

Buổi học bao gồm \(q\) sự kiện. Sau mỗi sự kiện, GSPVH muốn chương trình của bạn tìm ra tổng độ ngon của \(k\) món ngon nhất trên bàn để GSPVH lấy \(k\) món này. Nếu trên bàn có ít hơn \(k\) món, bạn hãy in ra tổng độ ngon của tất cả các món vì GS thừa khả năng cuốm hết mọi thứ đem đi. GSPVH chỉ ăn lượng lây hoa, ăn vì đam mê nên chỉ cần độ ngon không cần độ nhiều dưỡng chất. Các bạn hãy giúp GSPVH cute đối phó với sự troll của các sửu nhi nhé.

Input

• Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \le \theta \le 4)\) - số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên \(q\) và \(k\) \((1 \le k \le q \le 3\cdot 10^5)\), lần lượt là số sự kiện diễn ra và số đồ tối đa GSPVH có thể mang về.
• \(q\) dòng cuối cùng, mỗi dòng mô tả một sự kiện theo một trong hai khuôn dạng show t c (với \(1 \le t, c \le 10^7\)) hoặc eat.
• Dữ liệu vào đảm bảo độ hấp dẫn và lượng calories của các món ăn là đôi một phân biệt, và các học sinh chuyên Bắc Ninh chỉ lấy đồ ăn khi có ít nhất một món ăn đang ở trên bàn.

Output

• In ra \(q\) số nguyên thể hiện tổng độ ngon của (tối đa) \(k\) món ngon nhất đang có trên bàn sau mỗi sự kiện.

Example

1
12 3
show 1 3
show 2 6
show 3 5
show 4 1
show 5 2
eat
show 6 4
eat
eat
eat
eat
eat

1 3 6 9 12 12 15 15 10 9 4 0

Scoring

• Subtask \(1\) (\(20\) điểm): \(q \le 300\)
• Subtask \(2\) (\(20\) điểm): \(q \le 3000\)
• Subtask \(3\) (\(30\) điểm): Mọi thao tác loại 1 đều đứng trước mọi thao tác loại 2. Nói cách khác, sau khi chia nhau ăn món đầu tiên, không bạn học sinh nào đặt thêm đồ ăn lên bàn mời GSPVH.
• Subtask \(4\) (\(30\) điểm): Không có ràng buộc gì thêm.