Problem H: Sequence

Problem

項数$L$の等差数列が$N$個ある。$i$番目の等差数列の初項は$a_i$で公差は$d_i$である。1番目の数列から順番に1番目の数列, 2番目の数列, ..., $N$番目の数列と並べ、そうしてできた数列を$A$とする。その後、$A$から長さ$K$の任意の区間を選んで、新たに数列$B$を作るとき、数列$B$の和を最大化せよ。

Input

入力は以下の形式で与えられる。

$N$ $L$ $K$
$a_1$ $d_1$
$a_2$ $d_2$
...
$a_N$ $d_N$

1行目に3つの整数$N$, $L$, $K$が空白区切りで与えられる。
続く$N$行に、$i$個目の等差数列の情報$a_i$, $d_i$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq N \leq 10^5$
• $1 \leq L \leq 10^5$
• $1 \leq K \leq N\times L$
• $0 \leq a_i \leq 10^5$
• $1 \leq d_i \leq 10^3$
• 入力はすべて整数

Output

数列$B$の和の最大値を1行に出力する。

Sample Input 1

3 3 5
0 3
2 2
4 1

Sample Output 1

25

数列$A$は$0,3,6,2,4,6,4,5,6$となる。この数列の第5項から第9項までを数列$B$とすれば、数列$B$の和は25となり、これが最大である。

Sample Input 2

3 3 5
0 10
8 1
11 1

Sample Output 2

58

Note

Link

 

---