封印一擊

(seal.pas/c/cpp)

題目描述

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

輸入格式

第一行一個整數 N。 接下來 N 行每行兩個整數 ai、bi，第 i+1 行表示第 i 種元素的封印區間。

輸出格式

兩個用空格隔開的整數，第一個數是能夠獲得最多總能量的封印力度 E，第二個數是獲 得的總能量大小。當存在多個 E 能夠獲得最多總能量時，輸出最小的 E。

樣例輸入

2 5 10 20 25

樣例輸出

10 30

數據范圍與約定

對于 50% 的數據，1<=N<=1000，1<=ai<=bi<=10000。 對于 100% 的數據，1<=N<=10^5，1<=ai<=bi<=10^9。

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

正解思路：