购物

题目描述

有 $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

子任务	$n\le$	$m\le$	特殊性质	分值
$1$	$5$		N/A	$15$
$2$	$10^5$	$20$
$3$	$10^9$	$10^5$	$\max(b_i) \le \min(a_j)$	$20$
$4$			N/A	$50$

$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

子任务	$n\le$	特殊性质	分值
$1$	$200$	N/A	$15$
$2$	$5000$
$4$	$10^5$	$a_i$ 升序	$10$
$5$		N/A	$60$

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

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

---