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

تیمور که عاشق برق و برنامه‌نویسی بود، تصمیم گرفت که سیستم کنترل برق یک فروشگاه را به دست بگیرد. مدیر فروشگاه که هنوز به تیمور اطمینان نداشت، به او مسئولیتی سپرد تا او را بسنجد! او به تیمور مسئولیت محاسبه‌ی قیمت برق لامپ‌های فروشگاه را داد.

توضیح تصویر

فروشگاه دارای nn لامپ است که از ۱ تا nn شماره‌گذاری شده‌اند. لامپ‌های این فروشگاه شامل دو نوع سنسوری و کلیدی هستند:

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

علاوه بر ویژگی‌های گفته شده، هر لامپ یک مقدار pip_i دارد که نشان‌دهنده‌ی توان آن است. لامپ iiاُم به ازای هر یک ثانیه‌ای که روشن باشد، pip_i واحد انرژی مصرف می‌کند.

نحوه‌ی محاسبه‌ی هزینه‌ی برق برای لامپ‌ها نیز به صورت پله‌ای است. به طور دقیق‌تر، قیمت برق دارای kk پله است و پله‌ی iiاُم، دارای دو ویژگی EiE_i و PiP_i است که به ترتیب، نشان‌دهنده‌ی حداکثر میزان انرژی‌ای که در این پله قرار می‌گیرد و قیمت هر واحد انرژی مربوط به آن پله است.

برای محاسبه‌ی قیمت برق در یک ماه، تیمور ابتدا باید محاسبه کند که کل لامپ‌ها در کنار هم، چه مقدار انرژی مصرف کرده‌اند (این مقدار را EE در نظر می‌گیریم). سپس کوچکترین پله‌ی iiای را پیدا می‌کند که EiE_i آن، از مقدار مصرفی کل ماه، کمتر نباشد (EEiE \le E_i). پس از آن مقدار هر واحد انرژی در آن ماه را به دست می‌آورد که برابر با PiP_i می‌شود. در نتیجه قیمت کل انرژی مصرفی در آن ماه برابر با Pi×EP_i \times E خواهد بود.

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

فرض می‌کنیم در ابتدا، همه‌ی لامپ‌ها خاموش هستند.

ورودی

در خط اول ورودی عدد nn آمده است که نشان‌دهنده‌ی تعداد لامپ‌ها است. در خط iiاُم از nn خط بعدی، توضیح لامپ iiاُم آمده است. قالب توضیح هر لامپ نیز به صورت زیر خواهد بود:

قالب ورودی لامپ‌ها

قالب ورودی لامپ‌ها به یکی از شکل‌های زیر است:

SWITCH p_i
SENSOR p_i t_i
Plain text

خط اول نشان‌دهنده‌ی یک لامپ از نوع کلیدی با توان pip_i است و خط دوم نیز نشان‌دهنده‌ی یک لامپ سنسوری با توان pip_i و مهلت tit_i است.

1n1001 \le n \le 100 1pi2001 \le p_i \le 200 1ti1001 \le t_i \le 100

در خط بعدی، عدد kk آمده است که نشان‌دهنده‌ی تعداد پله‌های قیمت برق است. در خط iiاُم از kk خط بعدی نیز به ترتیب دو مقدار EiE_i و PiP_i آمده است که نشان‌دهنده‌ی حداکثر میزان انرژی پله‌ی iiاُم و قیمت هر واحد انرژی در آن پله است.

1k101 \le k \le 10 1Ei6×10101 \le E_i \le 6 \times 10 ^ {10} 1Pi1061 \le P_i \le 10 ^ 6

تضمین می‌شود مقدار EiE_iها و PiP_iها به صورت صعودی در ورودی می‌آیند و همچنین مقدار آخرین EiE_i حداقل به اندازه‌ی مجموع کل انرژی مصرفی است.

در خط بعدی عدد mm داده شده است که نشان‌دهنده‌ی تعداد گزارش‌ها است و در هر یک از mm خط بعدی نیز یک گزارش آمده است. قالب هر گزارش نیز به صورت زیر خواهد بود:

قالب ورودی هر گزارش

قالب ورودی هر گزارش به صورت زیر است:

LAMP_ID TIME
Plain text

که در آن LAMP_ID نشان‌دهنده‌ی شماره‌ی لامپی است که گزارش به آن تعلق دارد و TIME هم نشان‌دهنده‌ی زمانی است که آن تغییر رخ داده است. هر گزارش مربوط به یک لامپ است و در صورتی که لامپ مورد نظر از نوع سنسوری باشد، این گزارش بدان معناست که یک سیگنال برای این سنسور فرستاده شده است و اگر از نوع کلیدی باشد، یعنی وضعیت کلید آن لامپ تغییر کرده است (اگر لامپ روشن باشد، خاموش می‌شود و برعکس).

قالب TIMEها نیز تضمین می‌شود به شکل زیر خواهد بود:

DD hh:mm:ss
Plain text

که در آن DD و hh و mm و ss به ترتیب نشان‌دهنده‌ی روز و ساعت و دقیقه و ثانیه‌ی رخ دادن آن رخداد است.

1m1 0001 \le m \le 1\ 000 1LAMPIDn1 \le LAMP _ ID \le n 1DD311 \le DD \le 31 0hh230 \le hh \le 23 0mm590 \le mm \le 59 0ss590 \le ss \le 59 در صورتی که لامپی تا لحظه‌ی 31 23:59:59 روشن بود، فرض می‌کنیم در این لحظه خاموش می‌شود. همچنین فرض می‌کنیم ماهی که در آن هستیم ۳۱ روزه است و آخرین لحظه‌ی آن، لحظه‌ی 31 23:59:59 است.

تضمین می‌شود گزارش‌ها به ترتیب TIMEشان در ورودی می‌آیند.

خروجی

خروجی برنامه‌ی شما باید شامل یک خط باشد که مقدار هزینه‌ی برق در آن ماه را نشان می‌دهد.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۳۰ لامپ‌ها فقط از نوع کلیدی هستند
۲ ۵۰ لامپ‌ها فقط از نوع سنسوری هستند
۳ ۲۰ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2
SWITCH 1
SENSOR 2 2
4
2 1
5 3
11 4
15 5
4
1 01 00:00:00
1 01 00:00:05
2 01 00:00:10
2 01 00:00:11
Plain text

خروجی نمونه ۱

44
Plain text

ورودی نمونه ۲

2
SWITCH 19
SENSOR 200 11
4
190864635 992101
776902253 992469
785256700 992509
1071360000 999462
5
1 13 21:54:16
2 16 02:40:30
1 21 12:28:38
2 25 22:11:09
1 28 22:11:26
Plain text

خروجی نمونه ۲

17402369233425
Plain text

ورودی نمونه ۳

5
SWITCH 192
SWITCH 151
SWITCH 114
SWITCH 130
SWITCH 199
5
1747205084 11955
2653259616 296990
2669525672 525837
2674590960 538566
2678400000 599601
5
2 07 00:28:30
2 13 00:23:38
4 19 00:58:13
4 25 00:45:29
1 31 00:52:47
Plain text

خروجی نمونه ۳

1930822545060
Plain text

ورودی نمونه ۴

5
SENSOR 140 71
SENSOR 2 87
SENSOR 118 1
SENSOR 124 95
SENSOR 163 99
5
1773541254 973043
2355710147 992059
2414994190 997228
2481482739 998282
2678400000 998941
5
4 07 00:09:39
1 13 00:15:35
3 19 00:10:28
5 25 00:16:59
1 31 00:10:32
Plain text

خروجی نمونه ۴

46623355345
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.