C-小苯排雷_牛客周赛 Round 125

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯面前有一排 $n$ 个连续的格子，从左到右编号为 $1$ 到 $n$ 。某些格子中埋有地雷。
$\hspace{15pt}$ 每个地雷有一个手动引爆花费 $a_i$ 。如果 $a_i > 0$ ，表示第 $i$ 个格子中埋有地雷，且手动引爆它需要花费 $a_i$ ；如果 $a_i = 0$ ，表示该格子没有地雷。
$\hspace{15pt}$ 地雷之间可以相互引炸：一旦某个位置 $i$ 的地雷被引爆（无论是手动引爆还是被相邻地雷引爆），它会立即引爆其左右相邻（即位置 $i-1$ 和 $i+1$ ）的地雷（如果相应位置存在地雷且尚未被引爆）。这个过程会一直连锁反应下去，直到没有新的地雷被引爆。
$\hspace{15pt}$ 小苯希望通过手动引爆某些地雷，使得所有地雷最终都被引爆。他的目标是最小化手动引爆的总花费。
$\hspace{15pt}$ 你的任务是计算这个最小总花费。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示格子的数量。
第二行输入  个整数 ，表示每个格子中埋有地雷的手动引爆花费。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示引爆所有地雷的最小总花费。

示例1

输入

复制

2
5
2 0 3 3 4
6
0 0 1 0 0 2

输出

复制

5
3

说明

对于第一组测试数据，地雷在位置 ，花费分别为 。最优策略是手动引爆位置 ，花费 。