یک دانشمند نیمه‌دیوانه به نام ‎«زی»‎ در یک جزیره‌ی دورافتاده زندگی می‌کند. پس از سال‌ها تلاش و تحقیق، او موفق شده است که فرمول ‎«اکسیر جوانی»‎ را بیابد‎!‎ برای تهیه‌ی این اکسیر او به ‎۳‎ ماده‌ی ‎$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$‎ بشود، ‎«اکسیر جوانی‎» ساخته می‌شود.

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

• سوال بعد
• سوال قبل