قیمت نفت در بازارهای بورس تابع فاکتورهای زیادی است. یکی از این فاکتورها ‎«چشم و هم چشمی‎» میان کمپانی‌ها و کشورهای فعّال در بورس است‎!‎ برای مثال ممکن‌ست کشور بلیز‎ (یکی از کشورهای آمریکای لاتین که جمعیتش کمی بیش‌تر از باشگاه دانش‌پژوهان جوان است‎!‎) به‌تنهایی حاضر باشد نفت دریای شمال را حداکثر به‌قیمت بشکه‌ای ‎۸۰‎ دلار بخرد اما وقتی ببیند مثلاً ونزوئلا، اوگاندا، جزایر قناری، ساحل عاج و زامبیا (‎که مثلاً رقیب‌های اقتصادی بلیز است!)‎ دارند نفت می‌خرد، حاضر می‌شود تا ‎۸۵‎ دلار هم برای هر بشکه نفت بدهد. در سوی دیگر، کشورهای نفت‌خیز که فروشنده‌ی نفت هستند و از رقابت‌های اقتصادی میان کشورها خبر دارند، دوست دارند حداکثر فروش با سود مناسب را کرده و سود زیادی را در این میان به‌دست بیاورند.

آقای ‎«زی» (که اکسیر جوانی‌اش را نتوانست بسازد اما چیز دیگری ساخت و به خورد آقای ‎«کا»‎ داد و با قایق او فرار کرد‎(!‎ مشاور اقتصادی یک کمپانی بزرگ فروشنده‌ی نفت است. یک روز صبح رئیس کمپانی از او خواست تا با دانستن روابط اقتصادی میان کشورهای خریدار نفت و حداکثر ‎«ارزش اوّلیه‌ی نفت» (‎حداکثر پولی که آن کشور حاضرست در ابتدای کار و پیش از ‎«چشم و هم‌چشمی»ها برای نفت بپردازد) تک‌تک کشورها، یک قیمت ثابت و کلّی برای فروش نفت تعیین کند.

آقای ‎«زی»‎ می‌داند که هرگاه کشور ‎$X$‎ اقدام به خرید نفت کند، ارزش نفت در نزد هر کدام از کشورهایی که با ‎$X$‎ رقابت دارند و هنوز نفت نخریده‌اند، یک دلار افزایش می‌یابد. هم‌چنین هر کشور حداکثر یک‌بار اقدام به خرید نفت می‌کند و کشوری که ارزش‎ نفت (که با خرید نفت توسّط رقبایش افزایش می‌یابد) برایش بیش‌تر یا مساوی قیمت‎ نفت (که همواره ثابت است) بشود، در صورتی که هنوز نفت نخریده باشد، بلافاصله اقدام به‌خرید نفت می‌کند.

طبق اطلاعات داده شده به آقای ‎«زی»، در صورتی که قیمت نفت برابر ‎$V$‎ دلار باشد و در پایان کار ‎$n$‎ کشور نفت بخرند، سود نهایی کمپانی برابر ‎$nV$‎ می‌شود.

به آقای ‎«زی»‎ کمک کنید و برنامه‌ای بنویسید تا با دریافت ارزش اوّلیه‌ی نفت کشورها و رقابت‌های اقتصادی بین‌شان، قیمت نفت را طوری تعیین کند که بیش‌ترین سود عاید کمپانی بشود.

• در سطر اوّل ورودی، ‎$n$‎، تعداد کشورها، آمده است.
• در سطر دوم ‎$n$‎ عدد آمده است که عدد ‎$1\le i \le n$ (از سمت چپ) ارزش اوّلیه نفت در نزد کشور ‎$i$‎ را نشان می‌دهد.
• در سطر سوم ‎$e$‎ تعداد روابط رقابتی آمده است.
• در سطر های چهارم تا ‎$e+3$،‎اُم در هر سطر دو عدد ‎$X$‎ و سپس ‎$Y$‎ آمده است که حضور ‎$X~Y$‎ به این معنی‌است که ‎$X$ (عدد سمت چپ) چشم به ‎$Y$‎ دوخته است و اگر ‎$Y$‎ نفت بخرد، ارزش نفت در نزد ‎$X$‎ یک‌واحد افزایش می‌یابد. شماره کشورها از ‎$1$‎ تا ‎$n$‎ است.
• $0 \le e \le 5\times10^5$‎
• $1 \le n \le 10^5$‎، اما در ‎۸۰‎ درصد تست‌ها ‎$n \le 1000$‎ و در ‎۳۰‎ درصد تست‌ها ‎$n \le 100$‎ است.

در تنها سطر خروجی بهترین قیمت اوّلیه‌ی نفت را بنویسید که بیش‌ترین سود (حاصل‌ضرب قیمت‌اوّلیه در تعداد کل کشورهایی که نفت می‌خرند) را به کمپانی می‌رساند.

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

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