+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- تیمور که عاشق برق و برنامه‌نویسی بود، تصمیم گرفت که سیستم کنترل برق یک فروشگاه را به دست بگیرد. مدیر فروشگاه که هنوز به تیمور اطمینان نداشت، به او مسئولیتی سپرد تا او را بسنجد! او به تیمور مسئولیت محاسبه‌ی قیمت برق لامپ‌های فروشگاه را داد.  فروشگاه دارای $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$اُم آمده است. قالب توضیح هر لامپ نیز به صورت زیر خواهد بود: <details class="blue"> <summary>قالب ورودی لامپ‌ها</summary> قالب ورودی لامپ‌ها به یکی از شکل‌های زیر است: ``` text 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$$ </details> در خط بعدی، عدد $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$ خط بعدی نیز یک گزارش آمده است. قالب هر گزارش نیز به صورت زیر خواهد بود: <details class="blue"> <summary>قالب ورودی هر گزارش</summary> قالب ورودی هر گزارش به صورت زیر است: ``` 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` است.** </details> **تضمین می‌شود گزارش‌ها به ترتیب `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 ``` ## خروجی نمونه ۱ ``` 44 ``` ## ورودی نمونه ۲ ``` 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 ```