محل تقاطع خیابان استقلال که یک‌طرفه از شرق به غرب است و خیابان ولایت که یک‌طرفه از جنوب به شمال است، چهار راه فرهنگ نام دارد. هر کدام از دو خیابان مذکور، دو باند (صف) دارند که ماشین‌ها در هنگام ورود در آن دو قرار می‌گیرند تا پس از مدتی از چهار راه عبور کنند و به مسیر مستقیم‌شان ادامه دهند.

«آقای رسولی» که پلیس چهار راه است، در ابتدای هر ثانیه تصمیم می‌گیرد که ماشین‌های کدام یک از دو خیابان از چهار راه عبور کنند. پس از آن، ماشین ابتدایی هر یک از دو صف آن خیابان از چهار راه عبور کرده و سایر ماشین‌های آن خیابان یک واحد به جلو حرکت می‌کنند.

هیچ ماشینی دوست ندارد در ترافیک معطل بماند و اگر هنگام ورود به چهار راه با یک صف طولانی مواجه شود، به یک میزان قابل اندازه‌گیری عصبانی می‌شود! از این رو برای ماشین $i$، یک ضریب عصبانیت $C_i$ تعریف می‌کنیم که اگر هنگام ورود به چهار راه، در صفی قرار بگیرد که جلویش $k$ ماشین باشد، $k\times C_i$ واحد عصبانی می‌شود. دقت کنید که میزان عصبانیت برای هر ماشین تنها یک‌بار و آن هم در زمان ورودش و بسته به طول صف جلویش محاسبه می‌شود. هم‌چنین دقت کنید که ماشین‌ها پس از قرار گرفتن در یک صف نمی‌توانند جای‌شان را تغییر بدهند و هر ماشین به هنگام ورود در انتهای یکی از دو صف قرار می‌گیرد.

اکنون آقای رسولی با دانستن ضریب عصبانیت، زمان و جهت ورود هر ماشین به چهار راه می‌خواهد طوری برنامه‌ریزی کند که مجموع میزان عصبانیت ماشین‌ها کمینه شود. در ابتدای هر ثانیه او باید تعیین کند که ماشین‌های کدام یک از دو خیابان باید از چهار راه رد شوند. هم‌چنین او باید برای هر ماشین $i$، مشخص کند که به هنگام ورود، در صف سمت راست خیابان قرار بگیرد یا در صف سمت چپ آن. با این وصف اگر آقای رسولی بداند که ماشین $i$ با ضریب عصبانیت خیلی زیاد در زمان $t_i$ قرار است وارد چهار راه شود، می‌تواند سای ماشین‌های آن خیابان را طوری هدایت کند که ماشین مذکور، به هنگام ورود، پشت هیچ ماشینی نماند!

دقت کنید که عبور ماشین‌ها از چهار راه در ابتدای یک ثانیه و ورود ماشین‌های جدید به انتهای صف، در انتهای یک ثانیه اتفاق می‌افتد. نیز در صورتی که چند ماشین هم‌زمان در یک ثانیه وارد یک خیابان بشوند، آقای رسولی در رابطه با ترتیب ورودشان به صف و نحوه‌ی جای‌گیری‌شان مختار است. هم‌چنین می‌دانیم اگر آقای رسولی یک ماشین را طوری هدایت کند که جلویش بیش از $b$ ماشین باشد، راننده‌ی آن ماشین دچار «عصبانیت سرشار» شده و آقای رسولی را به قتل می‌رساند!

سطر نخست ورودی شامل دو عدد $n$(تعداد کل ماشین‌ها) و $b$ است.

در $n$ سطر بعدی، در هر سطر اطلاعات مربوط به یک ماشین نوشته شده است. در ابتدای سطر $i+1$ام، عدد $1\leq t_i$ که زمان ورود ماشین $i$ام است نوشته می‌شود، سپس یک کاراکتر $E$ یا $W$ در ادامه‌ی سطر می‌آید که به ترتیب بیان‌گر ورود ماشین از خیابان استقلال (شرق به غرب) یا خیابان ولایت (جنوب به شمال) است. نهایتا در انتهای همان سطر، $C_i$ که ضریب عصبانیت ماشین $i$ است نوشته می‌شود.( تمامی اعداد ورودی صحیح و نامنفی‌اند و $1\leq n \leq 100$ و $b\leq 30$‌ و $c_i \leq 10^4$ و $t_i\leq 10^8$ است)

اگر با هر نحوه‌ی برنامه‌ریزی، حالتی اتفاق می‌افتد که جلوی یک ماشین بیش از $b$ ماشین قرار می‌گیرد و راننده‌ی آن ماشین آقای رسولی را به قتل می‌رساند، در سطر اول خروجی، عبارت ire overflow! و در سطر دوم عدد $Q$، حداکثر تعداد ماشین‌هایی که می‌توانند در هنگام یا پیش از قتل آقای رسولی وارد یکی از صف‌ها شوند را بنویسید. بدیهی است ماشین فرد قاتل نیز جزو همین ماشین‌ها است. توجه کنید اگر در یک ثانیه آقای رسولی به قتل برسد، باید فرض کنید تمام ماشین‌هایی که در آن ثانیه می‌رسند، وارد چهار راه شده و در $Q$ به حساب می‌آیند.

اما در صورتی که آقای رسولی بتواند زنده بماند و بهترین برنامه‌ریزی را انجام دهد، در تنها سطر خروجی، کمینه‌ی مجموع میزان عصبانیت‌ها، پس از عبور تمامی ماشین‌ها را بنویسید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۱۰۰ مگابایت

• سوال بعد
• سوال قبل