You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

购物

题目描述

有 $m$ 种物品，每种物品有无限个，你可以购买 $n$ 个物品。

对于第 $i$ 种物品：

第一次买时的贡献是 $a_i$ ,接下来每购买一个的贡献都是 $b_i$。即当你买了 $x_i$ 个第 $i$ 种物品时，贡献是 $a_i+b_i \times (x_i-1)$

现在要你求出最大贡献。

输入格式

第一行一个 $t (1≤t≤10^4)$，表示有 $t$ 组数据。

对于每组数据：

第一行 $n$ 和 $m (1≤n≤10^9,1≤m≤10^5)$

接下来 $m$ 行，每行两个整数 $a_i$ 和 $b_i (0≤a_i,b_i≤10^9)$

每组数据后有一个空行。

输出格式

对于每组数据，输出一行一个整数表示最大的贡献。

样例

Input 1

2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1

Output 1

14
16

提示说明

Constraints

$t\le 10^4,0\le a_i,b_i\le 10^9,\sum m \le 3\times 10^5$

划分

题目描述

有 $n$ 栋连续的楼房，每栋楼有一个高度 $a_i$ 和价值 $b_i$。 现在，你需要把这 $n$ 栋楼房划分成若干个连续段，每一个连续段的价值为该段中最矮的楼房的价值。总的价值为每个连续段的价值之和。

你需要求出最大可能的总价值。

输入格式

第一行一个整数 $n$，表示楼房数。 第二行 $n$ 个整数，表示 $a_{1\dots n}$。 第三行 $n$ 个整数，表示 $b_{1\dots n}$。

输出格式

输出一行一个整数，表示最大的总价值。

样例

Input 1

5
1 2 3 5 4
1 5 3 2 4

Output 1

15

Input 2

5
1 4 3 2 5
-3 4 -10 2 7

Output 2

10

提示说明

Constraints

$-10^9 \le b_i\le 10^9$

$a$ 为一个长度为 $n$ 的排列