- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
صرافی ارز دیجیتال بیتپین $n$ رمزارز مختلف دارد که با اعداد $1$ تا $n$ شمارهگذاری شدهاند، هر کدام از رمزارزها دو رو دارند. یک رو قدرت که عدد نوشته شده بر آن عدد قدرت آن رمزارز نامیده میشود و آن را با $p_i$ نشان میدهیم. یک رو زیبایی که عدد نوشته شده بر آن عدد زیبایی آن رمزارز را مشخص میکند و آن را با $b_i$ نشان میدهیم.
![]() |
---|
سکه نماد رونق و ثروت است. |
دو عدد به نام اعداد زیبایی و قدرت سال وجود دارد که عدد زیبایی سال از بین اعداد زیبایی نوشته شده روی رمزارزها انتخاب میشود و عدد قدرت سال نیز از بین اعداد قدرت نوشته شده بر روی رمز ارزها انتخاب میشود. قدرت سال را با $P$ و زیبایی سال را با $B$ نشان میدهیم. هر رمزارز اگر حداقل یکی از عدد قدرت و یا زیبایی آن بیشتر و یا مساوی عدد متناظرش در سال باشد، میتواند بهجای سکه بر روی سفره هفت سین قرار بگیرد. به بیان دیگر رمزارز شمارهی $i$ روی میز قرار میگیرد اگر $p_i \geq P$ یا $b_i \geq B$ باشد ($1 \leq i \leq n$).
میخواهیم اعداد زیبایی و قدرت سال را از بین اعداد زیبایی و قدرتی که بین رمزارزها وجود دارد به شکلی تعیین کنیم که مجموع دو عدد تعیین شده برای زیبایی و قدرت بیشترین مقدار ممکن باشد و همچنین همه رمزارزهای بیتپین بتوانند بر روی سفره هفتسین قرار بگیرند.
برای شما $t$ بار این مسأله از اول مطرح میشود و هر بار از شما میخواهیم، این بیشترین مجموع را برای مسأله یا همان تست مد نظر خروجی دهید.
ورودی
در سطر اول عدد $t$، تعداد تستها میآید.
در اولین سطر هر تست، عدد صحیح $n$، تعداد بینکوینهای بیتپین میآید.
در دومین سطر هر تست، $n$ عدد صحیح $b_1, b_2, b_3, \cdots, b_n,,$ بهترتیب میآیند که نشاندهنده زیبایی رمزارزهای بیتپین است.
در سومین سطر هر تست، $n$ عدد صحیح $p_1, p_2, p_3, \cdots, p_n,,$ بهترتیب میآیند که نشاندهنده قدرت رمزارزهای بیتپین است.
$$1 \leq t \leq 200 , 000$$ $$ 1 \le n \le 200 , 000$$ $$ 1 \le b_i, p_i \le 10^9$$
تضمین میشود که مجموع $n$ برای همه $t$ تست حداکثر $200,000$ است.
خروجی
بیشترین مجموع ممکن با شرایط گفته شده برای زیبایی و قدرت سال را خروجی دهید.
مثالها
ورودی نمونه ۱
3
1
10
13
3
10 3 5
1 3 7
5
1 1 1 1 5
7 1 1 1 1
خروجی نمونه ۱
23
13
8
در این ورودی نمونه، ۳ تست مختلف وجود دارد:
- تست اول شامل ۱ رمزارز است. با توجه به اینکه اعداد زیبایی و قدرت از بین اعداد متناظر در رمزارزها باید انتخاب شوند پس عدد زیبایی سال برابر ۱۰ و عدد قدرت برابر ۱۳ خواهد بود، با مجموع ۲۳.
- در تست دوم بیشترین مجموع این است که ۱۰ را به عنوان عدد زیبایی و ۳ را به عنوان عدد قدرت انتخاب کنیم.
- در تست سوم با توجه به اینکه تعدادی رمزارز هستند که زیبایی و قدرت ۱ دارند؛ پس حداقل یکی از زیبایی و قدرت باید ۱ باشد که بتوانند در سفره هفت سین بیایند. بیشترین مجموع ممکن در این مثال را زیبایی ۱ و قدرت ۷ میسازد.
ارسال پاسخ برای این سؤال