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

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

‎ هیچ ماشینی دوست ندارد در ترافیک معطل بماند و اگر هنگام ورود به چهارراه با یک صف طولانی مواجه شود، به یک میزان قابل اندازه‌گیری عصبانی می شود‎!‎ از این رو برای ماشین ‎$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$‎ و در ‎$50$‎ درصد تست‌ها ‎$t_i \leq 100$‎ است‎.‎

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

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

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