Problem
Vers باید گزارشی در مورد آخرین پرواز آماده کند. او قبلاً متن را در ذهن خود ساخته است ، فقط نوشتن آن باقی مانده است. این گزارش از دو بخش تشکیل شده است: بخش اول حاوی n کلمه است، iکه شامل ai< است. / code> حروف، دوم — کلمات m که jمین آن از حروف bj تشکیل شده است. زبان کریا هیچ علامت نگارشی ندارد. Vers باید گزارش را روی یک رول کاغذ شطرنجی با عرض سلول w بنویسد. از آنجایی که گزارش از دو قسمت تشکیل شده است، رول را با یک خط عمودی به دو قسمت از کل عرض تقسیم می کند و پس از آن قسمت اول را در سمت چپ و در سمت راست — دوم.
هر دو بخش گزارش به یک شکل نوشته شده اند، هر کدام در قسمت خود از رول. یک حرف از کلمه دقیقا یک سلول را اشغال می کند. اولین کلمه در خط اول رول نوشته می شود و از سمت چپ ترین خانه این قسمت از رول شروع می شود. هر کلمه بعدی، در صورت امکان، باید در همان خط قبلی نوشته شود و دقیقاً با یک خانه خالی از آن جدا شود.
در غیر این صورت، در خط بعدی نوشته می شود و از سمت چپ ترین خانه شروع می شود. اگر عرض قسمتی از رول کمتر از طول کلمه ای باشد که باید در این قسمت نوشته شود، نوشتن این قسمت از گزارش روی قسمتی از رول با چنین عرضی غیرممکن است.
تضمین می شود که می توان یک نوار عمودی رسم کرد تا هر دو قسمت گزارش نوشته شود. Vers می خواهد یک خط عمودی بکشد تا طول رول که برای نوشتن گزارش کافی است حداقل باشد. به او کمک کنید حداقل طول را پیدا کند.
ورودی:
- سطر اول شامل سه عدد صحیح w، n و m — عرض رول، تعداد کلمات در قسمت اول و دوم گزارش (\(1 <= w <= 10^9\)؛ \(1 <= n، m <= 100 000\));
- خط بعدی n اعداد صحیح ai — طول کلمه i-ام قسمت اول گزارش \(1 <= a_i <= 10^9\);
- خط بعدی m اعداد صحیح bj — طول jمین کلمه قسمت دوم گزارش \(1 <= b_j <= 10^9\).
تضمین می‌شود که می‌توان یک خط کشید تا هر دو قسمت گزارش نوشته شود.
ورودی: در یک خط یک عدد صحیح را چاپ کنید — حداقل طول رول، که برای نوشتن گزارش کافی است.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
یادداشت
در آزمون نمونه، رول را می توان با کشیدن خطی بین ستون 7 و 8 سلول ها، و سپس نوشتن دو کلمه در هر خط در هر دو قسمت گزارش، به دو قسمت تقسیم کرد.