فهرست مندرجات
زی
یک دانشمند نیمه‌دیوانه به نام «زی» در یک جزیره‌ی دورافتاده زندگی می‌کند. پس از سال‌ها تلاش و تحقیق، او موفق شده است که فرمول «اکسیر جوانی» را بیابد! برای تهیه‌ی این اکسیر او به ۳ ماده‌ی $B$، $A$ و $C$ (به‌ترتیب به‌اندازه‌ی $r_B$، $r_A$ و $r_C$)احتیاج دارد.
پس از جست‌وجو در جزیره او موفق شده است $s_A$ واحد از ماده‌ی $A$ ،$s_B$ تا از $B$ و $s_C$ تا از $C$ پیدا بکند؛ اما این مقدار از مقدار لازم برای تهیه‌ی اکسیر کم‌تر است. از این رو، با روشن کردن آتش و فریاد زدن، او موفق شد با یک قایقران به‌نام «کا» آشنا بشود که می‌تواند مواد لازم را برای «زی» تهیه کند.
«کا» هر روز صبح با قایقش از کنار جزیره‌ی «زی» رد می‌شود و تعدادی «پیشنهاد معامله» برای «زی» دارد. هر پیشنهاد به‌صورت یک ۳تایی مرتّب $\langle O_a, O_b, O_c \rangle$ است که اگر $O_i$ منفی باشد به‌معنی دریافت از «زی» و اگر مثبت باشد به معنی پرداخت به «زی» است. برای مثال ۳تایی $\langle 2, -4, 5 \rangle$ به‌این معناست که «کا» حاضرست تا دقیقاً ۴ واحد از ماده‌ی $B$ از «زی» بگیرد و به‌جای آن ۲ واحد از ماده‌ی $A$ و ۵ واحد از ماده‌ی $C$ به «زی» بدهد.
«کا» هر روز تعدادی پیشنهاد برای «زی» می‌آورد و «زی» می‌تواند برخی (بین صفر تا همه) از آن‌ها را انتخاب کرده و طبق آن پیشنهادات با «کا» معامله کند. دقت کنید که از هر «پیشنهاد» در هر روز حداکثر یک‌بار می‌توان استفاده کرد. هم‌چنین پیشنهادات الزاماً باید به همان ترتیب گفته‌شدنشان قبول یا رد شوند؛ یعنی اگر «کا» در یک روز سه پیشنهاد برای «زی» بیاورد، «زی» نمی‌تواند اوّل پیشنهاد دوم را قبول و معامله کند، بعد پیشنهاد اوّل را.
واضح است که برای انجام یک پیشنهاد، مقدار ماده‌ای که «زی» دارد باید همواره بیش‌تر یا مساوی مقدار ماده‌هایی باشد که «کا» می‌خواهد. برای مثال، در پیشنهاد گفته شده در بالا اگر «زی» تنها $3$ واحد از ماده‌ی $B$ داشته باشد، قادر به انجام این معامله نیست؛ چرا که مقدار منفی از یک ماده (در پایان معامله) کاملاً بی‌معنی است!
از سوی دیگر، چون تنها محل مناسب برای نگه‌داری این مواد در جزیره، یک غار کوچک است، «زی» نمی‌تواند از هیچ یک از این سه ماده، به‌اندازه‌ی بیش‌تر از $V$ داشته باشد. دقت کنید که ممکن‌ست با انجام یک معامله مقدار یک از ماده‌ها از $V$ بیش‌تر شود، اما «زی» باید بلافاصله (و پیش از شروع معامله‌ی بعدی) این مقدار اضافه را بیرون بریزد. به‌عبارت بهتر، پیش از شروع هر معامله، مقدار ماده‌ی $A$، ماده‌ی $B$ و ماده‌ی $C$ در دست «زی» باید کم‌تر یا مساوی $V$ باشد.
می‌دانیم «کا» یک برنامه‌ی ماهیانه دارد؛ بدین معنی که اگر هر ماه دقیقاً $M$ روز باشد، «پیشنهاد»های روز $i$،اُمِ «کا» با «پیشنهاد»های روز «$M+i$»،اُمِ او برابرست.
نهایتاً می‌دانیم «زی» تنها تا $D$ روز دیگر زنده است و پس از پایان روز $D$اُم اگر به اکسیر جوانی دست نیافته باشد از دنیا می‌رود!
به «زی» کمک کنید و با دریافت پارامترهای مسئله، مقادیر اوّلیه و برنامه‌ی زمانی «کا»، برنامه‌ای بنویسید که زودترین زمانی را که «زی» می‌تواند به مواد لازم برای «اکسیر جوانی» برسد، مشخص کند.
ورودی
- در سطر اوّل ورودی، $V$، حداکثر مقدار هر کدام از ماده‌ها آمده است.
- در سطر دوم به‌ترتیب از چپ به راست مقادیر $s_A$، سپس $s_B$ و نهایتاً $s_C$ آمده است.
- مشابهاًدر سطر سوم، مقادیر $r_A, r_B, r_C$ (بالطّبع، اوّل $r_A$) نوشته شده است.
- در سطر چهارم، $M$ (تعداد روزهای تمام ماه‌ها) آمده است و در ادامه، در $M$ بلوک مشخّصات «پیشنهاد» های روزهای یکم تا $M$اُم ماه آمده است. ابتدای بلوک $i$ با یک عدد $n_i$ در یک سطر مشخّص می‌شود. سپس در $n_i$ سطر بعدی در هر سطر یک پیشنهاد به‌صورت $O_a, O_b, O_c$ نوشته می‌شود که شرایط گفته شده در بالا را دارد. دقت کنید که پیشنهادهای هر روز باید الزاماً به همان ترتیبی که در ورودی گفته می‌شود مورد بررسی قرار گرفته و اِعمال یا رد بشوند.
- نهایتاً در آخرین سطر ورودی $D$ نوشته می‌شود.
- دقّت کنید که اوّلین روز داستان، صبح روز یکم ماه است و برای مثال اگر $D=1$ باشد، در آن‌صورت «زی» یک‌روز برای معامله وقت دارد.
- تمام اعداد ورودی صحیح‌اند.
- $1 \le M \le 30$ و برای تمام روزهای ماه $0 \le n_i \le 7$ و هم‌چنین $0 \le D \le 365$.
- در هر کدام از سه‌تایی‌های گفته شده $0 \le r_i, s_i \le V$ و هم‌چنین در هر معامله $-V \le O_i \le V$.
- $0 \le V \le 30$؛ اما در ۸۰ درصد تست‌ها $V < 10$.
خروجی
- در تنها سطر خروجی در صورتی که «زی» می‌تواند پس از $d \le D$ روز به مواد لازم برای «اکسیر جوانی» برسد، مقدار $d$ را چاپ کنید.
- در غیر این‌صورت اگر پس از گذشت $D$ روز «زی» نمی‌تواند به «اکسیر» برسد، در خروجی ابتدا یک کلمه‌ی ««No (با N بزرگ و o کوچک)، سپس یک فاصله و در ادامه حداکثر مجموع مقدار ماده‌ای که «زی» می‌تواند پیش از مرگ داشته باشد را بنویسید. بالطبع این مقدار کم‌تر از $3V$ است!
- توجه داشته باشید که در اوّلین لحظه‌ای که مقدار ماده‌های $B$، $A$ و $C$ بیش‌تر مساوی (و نه لزوماً مساوی) $r_A$، $r_B$ و $r_C$ بشود، «اکسیر جوانی» ساخته می‌شود.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودي و خروجي نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
