seuOJ230 - 小雅米的旅途

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2019

题目描述

地图上有$n$座城市，小雅米要从 $n$ 号城市前往 $1$ 号城市。他可以话 $a$ 元乘汽车 $n$ 号城市前往 $n-1$ 号城市，他也可以花 $b$ 元乘汽车 $n$ 号城市前往 $n-2$ 号城市（注意如果小雅米在2号城市时他也能花 $b$ 元直接从 $2$ 号城市到 $1$ 号城市），他还可以花费 $c$ 元乘飞机从 $n$ 号城市前往 $\lfloor \frac n2 \rfloor$ 号城市。现在他想知道从 $n$ 号城市到 $1$ 号城市的最小花费是多少。

输入格式

第一行一个整数 $T(1\leq T\leq 10^5)$ 代表数据组数。 每组数据共一行四个数字 $n,a,b,c(1\leq n \leq 10^6，1\leq a,b,c \leq 10^9)$。

输出格式

每组数据一行一个整数代表从 $n$ 号城市到 $1$ 号城市的最小花费。

样例

输入样例

2
6 2 3 4
10 1 2 3

输出样例

7
7