در کتیبه‌های پیدا شده در سرزمین اقوام مایا آمده است که در روز قیامت زمین را آب فرا خواهد گرفت. در آن روز، خشکی‌های زمین به صورت تعدادی جزیره در می‌آیند و در هر جزیره تعدادی آدم ساکن خواهد بود. سپس خدایان پل‌های صراط را می‌سازند و یکی از خشکی‌ها را بهشت برین قرار می‌دهند. هر پل بین دو جزیره ساخته می‌شود و پل‌ها دو طرفه هستند.

خدایان پل‌ها را طوری می‌سازند که بین هر دو جزیره دقیقاً یک مسیر باشد. یعنی نقشه‌ی دنیا در روز قیامت، یک درخت خواهد بود‎!‎ هر کدام از پل‌های صراط ظرفیت محدودی دارد، بدین معنی که تعداد محدودی آدم می‌توانند از روی آن‌ها عبور کنند و ممکن است همه‌ی آدم‌ها نتوانند به بهشت بروند. از آنجا که خدایان بسیار بخشنده‌اند، می‌خواهند بیش‌ترین تعداد آدم‌ها بتوانند به بهشت بروند و از شما خواسته‌اند با گرفتن نقشه‌‌ی زمین در روز قیامت ، بگویید بهترین جزیره برای قرار دادن بهشت کدام جزیره است.

جزیره‌ای از همه بهتر است که با قرار دادن بهشت در آن بیش‌ترین تعداد آدم بتوانند به بهشت بروند. بدیهی است همه‌ی آدم‌ها دوست دارند به بهشت بروند و اگر بتوانند خود را به بهشت می‌رسانند.

• در سطر اول ورودی، عدد ‎$n$‎، تعداد جزیره ها قرار دارد. جزیره‌ها از ‎$1$‎ تا ‎$n$‎ شماره‌گذاری شده‌اند.‎
• در ‎$n$‎ سطر بعدی جمعیت جزیره‌ها آمده است .
• به این صورت که در سطر ‎$i$‎ام از این ‎$n$‎ سطر، جمعیت جزیره‌ی ‎$i$‎ام نوشته شده است.
• در ‎$n-1$‎ سطر بعدی، مشخصات پل‌ها داده شده است به این شکل که در هر سطر، شماره‌ی جزیره‌های دو سرِ یک پل و سپس ظرفیت آن پل با فاصله از هم نوشته شده است .
• ‎$1 \le n \le 1000000$‎.
• دیگر اعداد ورودی هم در محدوده‌ی ‎int‎ هستند.
• در حداقل ‎$20$ درصد تست‌ها ‎$n$‎ از ‎$10000$‎ بیش‌تر نیست.

در تنها سطر خروجی ابتدا بهترین مکان برای بهشت و سپس بیش‌ترین تعداد افرادی که به بهشت می رود را چاپ کنید.‎ در صورتی که بیش از یک مکان بهینه برای بهشت وجود دارد مکانی که کم‌ترین اندیس را دارد را به عنوان پاسخ چاپ نمایید.

• محدودیت زمان: ۶ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل