3799. [JZOI 2022 day1]恐狼后卫

【题目描述】

著名卡牌游戏《石炉传说》中有一张随从牌：恐狼后卫。恐狼后卫的能力是 使得相邻随从的攻击力提高。

现在有 $n$ 张恐狼后卫顺序排成一排，第 $i$ 只恐狼后卫的攻击力为 $a_i$ ，血量为 $h_i$ ，提升相邻随从的攻击力值为 $b_i$ 。

你的攻击力为 $atk$ ，每次攻击你可以选择一只存活的恐狼后卫，减少其血量值 $atk$ 。若其血量 $\leq\ 0$，则该恐狼后卫死亡。当某只恐狼后卫死亡时，其左右两侧（若存在）的恐狼后卫会靠拢并成为相邻 关系。

在攻击第 $i$ 只恐狼后卫时，除了要承受这只恐狼后卫自身的攻击力 $a_i$ 之外，还要承受与其相邻的 $2$ 张 恐狼后卫的提高攻击力值 $b_{i-1}$ 和 $b_{i+1}$（若存在）。

你的任务是承受最少的总伤害杀死所有恐狼后卫，输出需承受的伤害值。

【输入格式】

第一行一个正整数 $n$，表示恐狼后卫的数量。

第二行一个正整数 $atk$，表示你的攻击力。

以下 $n$ 行，每行 $3$ 个值：$a_i$ 、$b_i$ 、$h_i$ ，分别表示第 $i$ 只恐狼后卫自身的攻击力值、提升相邻随从的 攻击力值、血量值。

【输出格式】

一个整数，表示杀死所有恐狼后卫需要承受的最少伤害值。

【样例1输入】

3
1
8 1 6
3 5 7
4 9 2

【样例1输出】

94

【样例2输入输出】

点击下载样例2 

【数据规模与约定】

对于 $30\%$ 的数据，$n \leq 10$。

对于另外 $30\%$ 的数据，$n \leq 100，h_i=1$。

对于 $100\%$ 的数据，$n \leq 400，atk、a_i、b_i、h_i \leq 1000$。

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.22 pro3