- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بعد از خداحافظی کِشی و سفر او به جزایر ایبیزا برای گذراندن دوران بازنشستگی خود و خرج کردن میلیهای بدست آمده از مسابقه، آشمَز و صَفَر تصمیم گرفتند به یاد دوران خوشی که با هم گذراندند صندلی او را بازنشسته کنند.
آنها با این تغییر بزرگ نیاز به یک استراتژی جدید دارند. با توجه به هماهنگی بالای این تیم سربار جابهجا کردن کیبورد از سربار انتقال راهحل بیشتر است. پس آنها تصمیم میگیرند که بخش حل سوال و پیادهسازی راهحل را بین خود تقسیم کنند. به این صورت که صفر سوالها را حل میکند و دست به کیبورد نمیبرد و آشمز دائما پشت کیبورد است و حتی صورت سوالها را نمیخواند. صفر بعد از حل هر سوال راهحل آن را به آشمز انتقال میدهد و آشمز بلافاصله شروع به پیادهسازی آن میکند (انتقال راهحل زمانی نمیگیرد).
اما کشی هنوز دلسوز تیم است و دورادور عملکرد آنها را بررسی میکند. صفر و آشمز در یک ماراتون استقامت شرکت کردهاند. این ماراتون \(n\) سوال دارد. کشی که به خوبی به مهارتهای بچهها آشناست میداند حل سوال \(i\)-ام دقیقا \(a_i\) ثانیه از صفر وقت میگیرد و همچنین پیادهسازی آن دقیقا \(b_i\) ثانیه از آشمز وقت میگیرد. آنها تا فول کردن کانتست ادامه خواهند داد.
از آنجایی که استراتژی ترتیب حل سوالات از مهمترین عوامل موثر بر عملکرد است، کشی قصد دارد بهترین استراتژی ممکن را پیدا کند. اما از آنجا که او بازنشسته شده و در همین حین در سواحل در حال آفتاب گرفتن و نوشیدن یک لیوان پیناکولادا با دو نی هستند (که به جای لیوان در یک پوست نارگیل سرو میشود)، از شما میخواهد تا کمترین زمان لازم برای حل و پیادهسازی تمام سوالات را محاسبه کنید.
ورودی
در خط اول ورودی عدد \(t\)، تعداد تستکیسها آمده است. سپس از خط بعدی تستکیسها ورودی داده میشوند. در خط اول هر تستکیس، عدد \(n\) آمده است. و در هر کدام از \(n\) خط بعدی، در خط \(i\)امین خط، دو عدد \(a_i\) و \(b_i\) آمدهاند.
خروجی
برای هر تستکیس در یک خط جداگانه کمترین زمان لازم برای فول کردن کانتست را چاپ کنید.
محدودیتها
\[ 1 \leq t \leq 10^5 \] \[ 1 \leq n \leq 4 \cdot 10^5 \] \[ 1 \leq a_i, b_i \leq 10^6 \] \[ \sum n \leq 4 \cdot 10^5 \]
مثال
ورودی نمونه ۱
2
3
2 1
1 1
1 3
6
6 4
7 3
3 5
7 4
5 6
7 6
خروجی نمونه ۱
6
38
در تستکیس اول کافیست ابتدا سوال سوم، سپس سوال دوم و در آخر سوال اول را حل کنند تا در ۶ ثانیه کانتست رو فول کنن.