+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مدتی است که زورو به فکر خرید سرور است. زورو پس از بررسی‌های بسیار $n$ سرور مناسب پیدا کرده است که سرور $i$ام $C_i$ هسته دارد که هر کدام فرکانس $F_i$ دارد. قیمت سرور $i$ام نیز $V_i$ است. لازم به ذکر است که هسته‌های یک سرور از یک‌دیگر مستقل‌اند و می‌توانند کارهای متفاوتی را انجام دهند. زورو که به فکر کسب و کار است ، با جست و جوی فراوان $m$ مشتری پیدا می‌کند. مشتری $i$ام حاظر است که $v_i$ واحد پول به زورو بدهد به شرطی که زورو $c_i$ هسته از سرور (های)ش را که هر کدام حداقل فرکانس $f_i$ داشته باشد را به او اجاره دهد. لازم به ذکر است که هر هسته را می‌توان به حداکثر یک نفر اجاره داد. زورو که نمی‌خواهد این فرصت را از دست بدهد، از شما خواسته که به او کمک کنید و حداکثر سود ممکن را به او بگویید. # ورودی در خط اول ورودی $n$ ، تعداد سرورهای موجود برای خرید آمده است. در هر یک از $n$ خط بعدی سه عدد $C_i$ ، $F_i$ و $V_i$ آمده است که نشان‌دهنده مشخصات سرور $i$ام است. در خط بعدی ورودی $m$ ، تعداد مشتری های زورو آمده است. در هر یک از $m$ خط بعدی سه عدد $c_i$ ، $f_i$ و $v_i$ آمده است که نشان دهنده ی مشخصات مشتری $i$ام است. $$1 \le n, m \le 2\ 000$$$$1 \le C_i, c_i \le 50$$ $$1 \le F_i, f_i \le 10^9$$ $$1 \le V_i, v_i \le 10^9$$ # خروجی تنها یک عدد چاپ کنید که برابر با بیشینه سود ممکن زورو است. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۸ | $$n \le 15$$| | ۲ | ۱۸ | $$m \le 15$$| | ۳ | ۱۸ | $$n, m \le 250, C_i = c_i = 1$$| | ۴ | ۱۸ | $$F_i = f_i = 1$$| | ۵ | ۱۸ | $$V_i = v_i = 1$$| | ۶ | ۱۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550 ``` ## خروجی نمونه ۱ ``` 350 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- چند وقتی هست که زورو پول لازم هست. او به همین منظور سعی بر راضی کردن پدر خود دارد تا گونی پولی به او اهدا کند. پدرش که نگران درس زوروست با او قرار می‌گذارد که اگر او *پیشرفت تحصیلی* راضی کننده‌ای داشته باشد، به او یک گونی پول می‌دهد. منظور او از *پیشرفت تحصیلی* یک دنباله ای از آزمون‌های زورو است که اگر به ترتیب زمان مرتب شان کنیم، نمرات آن‌ها یک دنباله صعودی تشکیل دهند. مقدار راضی کنندگی یک پیشرفت تحصیلی برابر با تعداد آزمون‌های آن است. زورو که بد جور به فکر پول است ، می‌خواهد اخلاق را زیر پا بگذارد و تقلب کند. او یک بازه ی متوالی از لیست آزمون‌هایش (که به ترتیب زمان برگذاری مرتب شده اند) را به همراه عدد صحیح $d$ با رعایت $-x \le d \le x$ انخاب می‌کند و به تمام نمرات بازه انتخاب شده $d$ واحد اضافه می‌کند. دقت کنید که $d$ می‌تواند منفی باشد (ممکن است زورو غرق رد گم کردن شود و هدف اولیه خود را فراموش کند). حال او از شما خواسته که به دادش برسید. با گرفتن تعداد آزمون‌های زورو ($n$) و لیست نمرات او ($A$) و عدد $x$، مقدار راضی‌کننده‌ترین پیشرفت تحصیلی پس از تقلب را برایش چاپ کنید. # ورودی در خط اول ورودی به ترتیب دو عدد $n$ و $x$ با فاصله از هم آمده است. در خط دوم ورودی $n$ عدد با فاصله آمده‌اند که نشان دهنده لیست نمرات زورو اند. نمرات به ترتیب زمانی داده شده اند. $$1 \le n \le 200\ 000$$$$0 \le x , A_i \le 10^9$$ # خروجی تنها یک عدد چاپ کنید که برابر با بیشینه مقدار راضی کنندگی یک پیشرفت تحصیلی است. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۵ | $$n,x \le 10$$| | ۲ | ۱۰ | $$n,x \le 50$$| | ۳ | ۱۳ | $$n \le 1000$$| | ۴ | ۱۰ | $$x = 0$$ | | ۵ | ۲۰ | $$x \le 5$$ $$n \le 5 \times 10^4$$| | ۶ | ۱۷ | $$x = 10^9$$ | | ۷ | ۲۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 8 10 7 3 5 12 2 7 3 4 ``` ## خروجی نمونه ۱ ``` 5 ``` زورو می‌تواند بازه ی $[2,3]$ و $d = -5$ را انتخاب کند. بدین شکل $[-2,0,2,3,4]$ یک پیشرفت تحصیلی بهینه است.

**به محدودیت حافظه این سوال دقت کنید.** + محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۳۲ مگابایت ---------- زورو که نتوانست پدرش را راضی کند که در درسش پیشرفت داشته است، راه و چاره دیگری برای پول در آوردن پیدا کرد. او قصد دارد یک دنباله به طول $n$ از اعداد طبیعی را بر روی تکه کاغذی بنویسد و به دوست ریاضی دانش بفروشد! از آنجایی که پارسا می‌داند هیچ آدم عاقلی یک دنباله از اعداد را نمی‌خرد، سعی بر چرندبافی درباره ی این دنباله می‌کند. او ادعا می‌کند که اگر تمام زیردنباله‌های متوالی به طول $l$ دنباله اولیه را در نظر بگیریم، تعداد زیادی از آنها $k$*-متشابه* هستند. به دو دنباله هم طول $k$*-متشابه* می‌گوییم اگر تعداد اندیس‌های متناظرشان که یکسان نیستند حداکثر $k$ باشد. حال که زورو دنباله $a$ و عدد $l$ را انتخاب کرده است، می‌خواهد به ازای هر کدام از $n-l+1$ زیردنباله ی متوالی به طول $l$ بداند که با چند دنباله ی دیگر $k$-متشابه است. از آنجایی که او هنوز مقدار $k$ را مشخض نکرده است، $q$ بار از شما می‌خواهد که به ازای یک $k$ خاص پاسخ سوال او را بدهید. # ورودی در خط اول ورودی به ترتیب دو عدد $n$ و $l$ آمده است. در خط دوم ورودی $n$ عدد با فاصله آمده‌اند که نشان دهنده دنباله زورو اند. در خط سوم ورودی $q$، تعداد پرسش‌های زورو آمده است. در هر یک از $q$ خط بعدی یک عدد $k_i$ آمده که پرسش زورو را مشخص می‌کند. $$1 \le l \le n \le 10\ 000$$$$1 \le a_i \le 10^9$$ $$1 \le q \le 100$$ $$0 \le k_i \le l$$ # خروجی در هر یک از $q$ خط خروجی ، $n-l+1$ عدد چاپ کنید که عدد $i$ام سطر $j$ام نشان دهنده تعداد زیردنباله‌های متوالی است که با زیردنباله $i$ام $k_j$-متشابه هستند. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۵ | $$n \le 300$$| | ۲ | ۲۰ | $$n \le 2000$$| | ۳ | ۲۰ | $$q = 1, k_1 = 0$$| | ۴ | ۱۵ | $$q = 1$$ | | ۵ | ۲۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 6 2 1 2 1 3 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 2 1 1 1 1 4 4 4 4 4 ```

نمره‌دهی سوالات در حالت عادی نمره هر سوال با توجه به تعداد تست‌هایی که درست جواب داده می‌شوند، تقسیم بر تعداد کل تست‌ها معلوم می‌شود. در صورتی که بخواهید نمره‌دهی به این گونه نباشد می‌توانید از تست‌ها را به تعدادی دسته تقسیم کنید و به ازای هر دسته یک نمره تعیین کنید که اگر همه تست‌های آن دسته درست جواب داده شوند، نمره آن دسته به کاربر داده می‌شود. برای استفاده از این قابلیت شما می‌توانید در کنار تست‌ها یک فایل به نام config.json قرار دهید که در آن یک شی JSON قرار دارد و یک لیست به نام packages دارد که هر عضو آن یک دیکشنری است و دو ویژگی به نام score و tests دارد. score نمره آن دسته از تست‌ها و tests یک لیست شامل شماره آن تست‌ها می‌باشد. توجه کنید که جمع score دسته‌ها لازم نیست عدد خاصی شود و در نهایت نمره اصلی یک ارسال با توجه به نمره اصلی سوال که در بخش تنظیمات سوال وارد می‌شود محاسبه می‌شود. برای مثال در [این سوال](https://quera.ir/problemset/olympiad/32473/%D8%B3%D8%A4%D8%A7%D9%84-%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87%D9%86%D9%88%DB%8C%D8%B3%DB%8C-%D9%BE%D9%88%DB%8C%D8%A7-%D8%B2%D9%88%D8%B1%D9%88-%D8%AF%D9%86%D8%A8%D8%A7%D9%84%D9%87-%D9%85%DB%8C%D9%81%D8%B1%D9%88%D8%B4%D8%AF) تست‌ها دسته بندی شدند و به ازای هر دسته اطلاعات مربوط در فایل config.json وارد شده است. می‌توانید تست‌های این سوال را از [این‌جا](https://quera.ir/qbox/download/gn4qZNzxIF/zoro.zip) ببینید.