====== قیمت نفت ====== قیمت نفت در بازارهای بورس تابع فاکتورهای زیادی است. یکی از این فاکتورها ‎«چشم و هم چشمی‎» میان کمپانی‌ها و کشورهای فعّال در بورس است‎!‎ برای مثال ممکن‌ست کشور بلیز‎ (یکی از کشورهای آمریکای لاتین که جمعیتش کمی بیش‌تر از باشگاه دانش‌پژوهان جوان است‎!‎) به‌تنهایی حاضر باشد نفت دریای شمال را حداکثر به‌قیمت بشکه‌ای ‎۸۰‎ دلار بخرد اما وقتی ببیند مثلاً ونزوئلا، اوگاندا، جزایر قناری، ساحل عاج و زامبیا (‎که مثلاً رقیب‌های اقتصادی بلیز است!)‎ دارند نفت می‌خرد، حاضر می‌شود تا ‎۸۵‎ دلار هم برای هر بشکه نفت بدهد. در سوی دیگر، کشورهای نفت‌خیز که فروشنده‌ی نفت هستند و از رقابت‌های اقتصادی میان کشورها خبر دارند، دوست دارند حداکثر فروش با سود مناسب را کرده و سود زیادی را در این میان به‌دست بیاورند. آقای ‎«زی» (که اکسیر جوانی‌اش را نتوانست بسازد اما چیز دیگری ساخت و به خورد آقای ‎«کا»‎ داد و با قایق او فرار کرد‎(!‎ مشاور اقتصادی یک کمپانی بزرگ فروشنده‌ی نفت است. یک روز صبح رئیس کمپانی از او خواست تا با دانستن روابط اقتصادی میان کشورهای خریدار نفت و حداکثر ‎«ارزش اوّلیه‌ی نفت» (‎حداکثر پولی که آن کشور حاضرست در ابتدای کار و پیش از ‎«چشم و هم‌چشمی»ها برای نفت بپردازد) تک‌تک کشورها، یک قیمت ثابت و کلّی برای فروش نفت تعیین کند. آقای ‎«زی»‎ می‌داند که هرگاه کشور ‎$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$‎ است. ===== ‎‎خروجی ===== در تنها سطر خروجی بهترین قیمت اوّلیه‌ی نفت را بنویسید که بیش‌ترین سود (حاصل‌ضرب قیمت‌اوّلیه در تعداد کل کشورهایی که نفت می‌خرند) را به کمپانی می‌رساند. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودي و خروجي نمونه ===== ^ ورودي نمونه ^ خروجي نمونه ^ |3 \\ 8 9 10 \\ 3 \\ 1 3 \\ ‎1 2 \\ 2 3‎|‎30‎| |4 \\ 4 3 2 1 \\ 5 \\ ‎2 1 \\ ‎4 1 \\ ‎1 4‎ \\ ‎4 2 \\ ‎3 4‎|‎‎12‎| * [[سوال ۱۴|سوال بعد]] * [[سوال ۱۲|سوال قبل]]