题目描述

有$n$ 头狼排成一排，每只狼两个属性，攻击力 $a_i$ 和加成值 $b_i$，狼的实际攻击力等于自身攻击力加相邻狼的加成值，被杀死之后的狼对相邻的狼的攻击力的加成会被取消，同时，原先与 被杀死的狼相邻的两头狼会变成相邻的狼。问杀死所有狼受到的伤害值最小是。

输入格式

多组输入，第一行一个 $T$