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

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

توضیح تصویر

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

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

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

نحوه‌ی محاسبه‌ی هزینه‌ی برق برای لامپ‌ها نیز به صورت پله‌ای است. به طور دقیق‌تر، قیمت برق دارای $k$ پله است و پله‌ی $i$ اُم، دارای دو ویژگی $E_i$ و $P_i$ است که به ترتیب، نشان‌دهنده‌ی حداکثر میزان انرژی‌ای که در این پله قرار می‌گیرد و قیمت هر واحد انرژی مربوط به آن پله است.

برای محاسبه‌ی قیمت برق در یک ماه، تیمور ابتدا باید محاسبه کند که کل لامپ‌ها در کنار هم، چه مقدار انرژی مصرف کرده‌اند (این مقدار را $E$ در نظر می‌گیریم). سپس کوچکترین پله‌ی $i$ ای را پیدا می‌کند که $E_i$ آن، از مقدار مصرفی کل ماه، کمتر نباشد ( $E \le E_i$ ). پس از آن مقدار هر واحد انرژی در آن ماه را به دست می‌آورد که برابر با $P_i$ می‌شود. در نتیجه قیمت کل انرژی مصرفی در آن ماه برابر با $P_i \times E$ خواهد بود.

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

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

ورودی

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

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

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

SWITCH p_i
SENSOR p_i t_i

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

$1 \le n \le 100$ $1 \le p_i \le 200$ $1 \le t_i \le 100$

در خط بعدی، عدد $k$ آمده است که نشان‌دهنده‌ی تعداد پله‌های قیمت برق است. در خط $i$ اُم از $k$ خط بعدی نیز به ترتیب دو مقدار $E_i$ و $P_i$ آمده است که نشان‌دهنده‌ی حداکثر میزان انرژی پله‌ی $i$ اُم و قیمت هر واحد انرژی در آن پله است.

$1 \le k \le 10$ $1 \le E_i \le 6 \times 10 ^ {10}$ $1 \le P_i \le 10 ^ 6$

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

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

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

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

LAMP_ID TIME

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

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

DD hh:mm:ss

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

$1 \le m \le 1\ 000$ $1 \le LAMP _ ID \le n$ $1 \le DD \le 31$ $0 \le hh \le 23$ $0 \le mm \le 59$ $0 \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

خروجی نمونه ۱

ورودی نمونه ۲

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

خروجی نمونه ۲

17402369233425

ورودی نمونه ۳

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

خروجی نمونه ۳

1930822545060

ورودی نمونه ۴

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

خروجی نمونه ۴

46623355345

ارسال پاسخ برای این سؤال