阿源的田地 3

題目敘述

阿源裝好果子後要將他們送到城鎮去販賣，現在要去的城鎮有$n(n\leq 1e5)$個，阿源也剛好有$n$台車，根據交通壅塞程度，通過通往第$i$個城鎮所需時間為$a_it + b_i$，$a_i$及$b_i$為道路係數，$t$為一個經過簡化後的時間係數，必須為整數且要使所有道路的$a_it + b_i \geq 0$，當車子開上路後係數就不會變了，現在請你選擇一個時間係數，使得最晚到達城鎮的車子越早到越好。

輸入說明

輸入的第一行包含一個整數 $T(T\leq 100)$，代表有 $T$ 次收穫需要運送，每次收穫運送第一行會有一個數字，第一個為 $n$ 代表需要去的城鎮數量$\sum n \leq 1e6$，接下來有$n$行，第$i$行有兩個數字$a_i b_i$ ，代表通往第$i$個城鎮的道路係數。

輸出說明

對於每次運送，請輸出一個整數代表最晚到達城鎮的車子最早能多早到。

範例輸入

範例輸出

50
75

範例解釋

第一筆的最佳時間係數為50 第二筆的最佳時間係數為$25\sim75$所有整數

子題一[10%]

$n \leq 100 $ $0\leq |a_i| , b_i \leq 100$

子題二[20%]

$n \leq 100 $ $0\leq |a_i| , b_i \leq 1e9$

子題三[20%]

$n \leq 1e5 $ $0\leq |a_i| , b_i \leq 100$

子題四[35%]

$n \leq 1e5 $ $0\leq |a_i| , b_i \leq 1e9$

子題五[5%]

$n \leq 1e5 $ $0\leq |a_i| , b_i \leq 1e18$

Judge Setting

run-time limit: 1000 ms
memory limit: 10000000 byte
測資數量: 5