- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک رستوران \(k\) آشپز کار میکنند. \(n\) پاستا پنه آلفردو باید آماده شود. هر حاضرسازی ۳ مرحله دارد و برخی مراحل حاضرسازی میتواند همزمان انجام شود. برای حاضر کردن \(i\)امین آنها باید ابتدا یکی از آشپزها \(a_i\) دقیقه پاستای آن را حاضر کند و روی میز ۱ بگذارد. سپس یکی از آشپزها پاستای آن را از روی میز ۱ بردارد و در \(b_i\) دقیقه پاستا پنهی آن را حاضر کند و روی میز ۲ بگذارد. سپس یکی از آشپزها پاستا پنهی آن را از روی میز ۲ بردارد و در \(c_i\) دقیقه پاستا پنه آلفردو را حاضر کند و تحویل مشتری دهد. یک محدودیت مهم، این است که روی میز ۱ حداکثر \(x\) پاستا و روی میز ۲ حداکثر \(y\) پاستا پنه جا میشود. برنامهای برای کار کردن آشپزها ارائه دهید که زمان آمادهسازی این \(n\) پاستا پنه آلفردو به وسیلهی \(k\) آشپز رستوران کمینه شود.
آشپزها با اندیسهای ۱، ۲، ۳، ... \(k\) شمارهگذاری شدهاند.
مدت زمان برداشتن یا گذاشتن پاستاها روی میز و تحویل دادن آن به مشتری ناچیز است و میتوان آن را ۰ در نظر گرفت.
دقت کنید که بعد از اینکه آشپزی حاضرسازی را انجام داد باید پاستا را روی میز بگذارد یعنی اگر در زمان \(t\) آشپزی پاستا را حاضر کرد، آن را روی میز میگذارد و ممکن است آشپز دیگری در همان لحظه پاستا را از روی میز بردارد ولی نباید در زمان \(t\) بیشتر از حد مجاز پاستا روی میز باشد. به عبارت دیگر در زمان \(t\)، پاستا روی میز است مستقل از اینکه آشپز دیگری آن را درلحظه \(t\) بردارد.
اگر آشپزی در زمان \(t\) پاستا را بردارد و حاضرسازی آن \(m\) دقیقه طول بکشید در دقیقا زمان \(t+m\) باید پاستا را روی میز بگذارد و نمیتواند دیرتر یا زودتر آن را روی میز بگذرد.
آشپزها تنها در زمانهایی که به دقیقه حسابی هستند میتوانند شروع به انجام کاری کنند. (یعنی زمان ۰، ۱، ۲، ۳، ...)
دقت کنید که هرگاه یک آشپز درگیر یک حاضرسازی بشود (مثلاً حاضر کردن پاستا، یا حاضر کردن پاستا پنه آلفردو از روی پاستا پنه)، باید آن حاضرسازی را بطور کامل انجام دهد و سپس سراغ کار بعدی خود برود. همچنین هر آشپز در هر لحظه یک حاضرسازی میتواند انجام دهد.
در این سوال هرچه برنامهی شما بهینهتر باشد و در زمان کمتری همهی پاستا پنه آلفردوها حاضر شود، نمرهی بیشتری دریافت میکنید. به عبارت دیگر نیازی نیست در کمترین زمان ممکن همهی پاستا پنه آلفردوها را آماده کنید و نمرهی شما از این سوال صرفاً به اختلاف زمان حاضر کردنی که شما به دست میآورید و جواب کمینه مسأله بستگی دارد.
ورودی
در خط اول ورودی به ترتیب چهار عدد \(n\) (تعداد پاستاها)، \(k\) (تعداد آشپزها)، \(x\) (تعداد پاستا ای که روی میز ۱ جا میشود)، \(y\) (تعداد پاستا پنه ای که روی میز ۲ جا میشود). و سپس در \(n\) خط بعدی در هر خط ۳ عدد \( a_i, b_i, c_i \) آمده است که به ترتیب زمان مورد نیاز برای حاضر کردن پاستا، پاستا پنه و پاستا پنه آلفردو \(i\) ام است.
\[ 1 \le n,x,y,k \le 1\ 000 \] \[ 1 \le a_i , b_i , c_i \le 1\ 000 \ 000 \]
خروجی
خروجی شما ترتیب حاضر سازیها است که باید شامل \(3n\) خط باشد که در خط \(i\) ام شما باید سه عدد \(t_i, s_i, f_i \) خروجی دهید که به این معناست که در دقیقه \(t_i\) آشپز \(s_i\) به حاضر سازی \(f_i\) امین غذا میپردازد (اگر پاستا آن حاضر بود آن را به پاستا پنه تبدیل میکنید و اگر پاستا پنه آن حاضر بود به پاستا پنه آلفردو تبدیل میکند و گرنه پاستا آن را حاضر می کند) . خروجی شما باید معتبر باشد یعنی شرطهای زیر برای آن برقرار باشد:
\[ 0 \le t_i \le 3\times10^{9} \] \[ 1 \le s_i \le k \] \[ 1 \le f_i \le 1\ 000 \]
در لحظه \(t_i\) پاستا \(f_i\) درحال آماده سازی نباشد و آشپز مشغول آماده سازی پاستا دیگری نباشد. (ممکن است در لحظه \(t_i\) کار آشپز تمام شود و کار دیگری را شروع کند و یا در آن لحظه پاستا به مرحله بعدی آماده سازی برود و آشپز پاستا را در همان لحظه از روی میز بردارد)
نباید پاستا ای را بیشتر از ۳ بار در خروجی چاپ کنید.
هیچ گاه روی میزی بیشتر از حد مجازش پاستا نباشد.
برای هر \( 2 \le i \) : \( t_{i-1} \le t_i \)
برای هر تست در صورتی که خروجی شما معتبر نباشد نمرهی آن تست را نمیگیرید.
مثال
ورودی نمونه ۱
3 2 1 2
1 5 5
2 1 1
3 2 5
خروجی نمونه ۱
0 1 1
0 2 2
1 1 1
2 2 2
3 2 3
6 1 3
6 2 2
7 2 1
8 1 3
زمانی که طول میکشد تا همه پاستا پنه آلفردوها حاضر شود ۱۳ دقیقه است و زودتر از این زمان نمیشود تمام پاستا پنه آلفردوها را حاضر کرد.