封印一擊

(seal.pas/c/cpp)

題目描述

“圣主 applepi 于公元 2011 年 9 月創(chuàng)造了 Nescafe，它在散發(fā)了 16 次光輝之后與公元2011 年 11 月 12 日被封印為一顆魂珠，貯藏于 Nescafe 神塔之中。公元 2012 年 9 月，圣主帶領(lǐng)四大護(hù)法重啟了 Nescafe，如今已經(jīng)是 Nescafe 之魂的第 30 次傳播了。不久，它就要被 第二次封印，而變成一座神杯……”applepi 思索著 Nescafe 的歷史，準(zhǔn)備著第二次封印。 Nescafe 由 n 種元素組成（編號(hào)為 1~n），第 i 種元素有一個(gè)封印區(qū)間[ai,bi]。當(dāng)封印力度E 小于 ai 時(shí)，該元素將獲得 ai 的封印能量；當(dāng)封印力度 E 在 ai 到 bi 之間時(shí)，該元素將獲得E 的封印能量；而當(dāng)封印力度 E 大于 bi 時(shí)，該元素將被破壞從而不能獲得任何封印能量。 現(xiàn)在圣主 applepi 想選擇恰當(dāng)?shù)?E，使得封印獲得的總能量盡可能高。為了封印的最后一擊 盡量完美，就請(qǐng)你寫個(gè)程序幫他計(jì)算一下吧！

輸入格式

第一行一個(gè)整數(shù) N。 接下來 N 行每行兩個(gè)整數(shù) ai、bi，第 i+1 行表示第 i 種元素的封印區(qū)間。

輸出格式

兩個(gè)用空格隔開的整數(shù)，第一個(gè)數(shù)是能夠獲得最多總能量的封印力度 E，第二個(gè)數(shù)是獲 得的總能量大小。當(dāng)存在多個(gè) E 能夠獲得最多總能量時(shí)，輸出最小的 E。

樣例輸入

2 5 10 20 25

樣例輸出

10 30

數(shù)據(jù)范圍與約定

對(duì)于 50% 的數(shù)據(jù)，1<=N<=1000，1<=ai<=bi<=10000。 對(duì)于 100% 的數(shù)據(jù)，1<=N<=10^5，1<=ai<=bi<=10^9。

思路想對(duì)了，沒敢寫，暴力50分，果然是做題太少了。

正解思路：