المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۲۲

بر بال کرکس

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

یه خرده بهش کمک کنید، ببینید چقدر تمشک می‌تونه به مقصد برسونه.

ورودی

در سطر اول فایل ورودی $n$ تعداد بازه‌های تمشکی و سپس به ترتیب مختصات خونه‌ی البرز و باشگاه اومده.

در سطر بعد ابتدا سرعت ثابت کرکس در جهت جنوب و سپس حداکثر سرعت شرق و غرب رفتن البرز آمده است.

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

خروجی

در تنها سطر خروجی یک عدد بنویسید که حداکثر تعداد تمشک‌های جمع‌آوری شده توسط البرزه.

توجه

می‌دانیم $1\leq n \leq 200$ و هر مختصه‌ی یک خانه در بازه‌ی $[0...10^5]$ قرار دارد. البرز حتما می‌تواند به باشگاه برسد. همه‌ی اعداد ورودی صحیح هستند. بازه‌های ورودی دو سر بسته می‌باشند و با یک‌دیگر اشتراک ندارند.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3 6 50 0 0
10 5
6 10 16 10 10
6 20 16 20 5
0 20 5 20 4
5

ابزار صفحه