- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
باربری طلا در شرکت میلی، توسط دو قطار سریعالسیر مخصوص انجام میشود که ریلهای آنها مانند دو خط صاف موازی، کنار یکدیگر قرار گرفتهاند. تعدادی ایستگاه تخلیه بار بین این دو ریل و در امتداد ریلها وجود که با نامهای \(0\) الی \(X\) نام گذاری شدهاند.
هر ریل مخصوص یک قطار است و هر قطار همیشه بر روی ریل مربوط به خودش حرکت میکند. در ابتدا یک قطار در ایستگاه \(0\) است و جهت حرکت آن به سمت ایستگاه \(X\) است و دیگری در ایستگاه \(X\) قرار دارد و جهت حرکت آن به سمت ایستگاه \(0\) است. قطارها از ابتدا ثانیه \(0\) شروع به حرکت میکنند. و در جهت حرکتشان هر ثانیه به اندازه فاصله بین دو ایستگاه، به جلو میروند (بعد از \(X\) ثانیه به ایستگاه آخر در جهت حرکتشان میرسند). هر قطار بعد از رسیدن به ایستگاه آخر، بلافاصله و بدون از دستدادن زمان، جهت حرکتش را عوض میکند و در ریل قبلی خودش به سمت مخالف شروع به حرکت میکند.
به دلیل قیمت بالا طلا، کارکنان شرکت میلی خودشان شخصا باربری طلاها را با قطار انجام میدهند. هر کارمند در زمان مشخصی (برای هر کارمند میتواند متفاوت یا تکراری باشد) با بسته طلا در دستش وارد یکی از ایستگاههای \(0\) یا \(X\) میشود و میخواهد که سوار قطار شده و در ایستگاه مقصد مشخصی پیاده شود و بسته طلا را تحویل دهد. او در ایستگاه مبدا منتظر میماند و هرگاه قطاری در آن ایستگاه در حال شروع حرکت باشد، سوار میشود و هنگام رسیدن قطار به ایستگاه مقصد، از قطار پیاده میشود. بسته را تحویل میدهد و سپس همانجا ناپدید میشود (به دلیل استرس زیاد از حمل طلا). پیاده و سوار شدن مسافران هزینه زمانی ندارد.
میدانیم هر گاه این دو قطار از کنار هم عبور کنند، همه کارکنانی که در هر دو قطار هستند برای همهی کارکنان قطار روبهرویی دست تکان میدهند (حتی آنهایی که میخواهند در همان نقطه از قطار پیاده شوند). هر فرد به اندازه تعداد نفراتی که برای آنها دست تکان داده است خوشحال میشود. خوشحالی شرکت میلی بعد از اتمام باربری، برابر است با مجموع خوشحالی کارکنان آن تقسیم بر دو (به ازای هر دو نفر یک واحد). پس شرکت میلی دوست دارد که مجموع خوشحالی را بیشینه کند.
میلی به شما عدد \(k\) را ورودی میدهد و از شما میخواهد حداکثر \(k\) نفر از کارمندانی که ایستگاه مبدا آنها 0 است را انتخاب کنید و زمان رسیدن آنها به مبدا را طوری تغییر دهید که در نهایت خوشحالی بیشینه شود. این خوشحالی بیشینه را خروجی دهید.
ورودی
ورودی شامل تعدادی سناریو مختلف است. در خط اول هر ورودی عدد \(T\)، تعداد سناریوها ورودی داده میشود. سپس در خط اول هر سناریو به ترتیب سه عدد \(n\) و \(X\) و \(k\) داده میشود. سپس در خط \(i\)ام از هر کدام از \(n\) خط بعدی، سه عدد \(dir_i\) و \(time_i\) و \(pos_i\) داده میشود که نشاندهنده مبدا، زمان رسیدن به مبدا و ایستگاه مقصد کارمند \(i\)ام است. در صورتی که \(dir_i\) برابر 0 باشد یعنی مبدا این کارمند ایستگاه 0 است. در غیر اینصورت برابر 1 است و یعنی ایستگاه \(X\) مبدا این کارمند است.
\[ \sum n \leq 2 \cdot 10^5 \] \[ 0 \leq time_i, pos_i\leq 10^9 \] \[ 1 \leq X \leq 10^9 \]
خروجی
برای هر سناریو، بیشینه خوشحالی را بعد از \(k\) تغییر، در یک خط جداگانه چاپ کنید.
مثال
ورودی نمونه ۱
2
6 4 0
0 3 2
1 4 1
0 5 1
0 6 3
1 7 0
1 8 2
6 4 1
0 3 2
1 4 1
0 5 1
0 6 3
1 7 0
1 8 2
خروجی نمونه ۱
3
4
در نمونهی اول، در زمان \(6\) یک قطار حاوی شخص \(1\) و یک قطار حاوی شخص \(2\) به هم میرسند. در زمان \(10\) یک قطار حاوی شخص \(4\) و یک قطار حاوی شخص \(5\) و \(6\) به هم میرسند.
در نمونهی دوم، کافیست زمان شخص \(1\) را به \(5\) تغییر دهیم.