问题 L: 恐狼后卫 问题 L: 恐狼后卫
时间限制: 1 Sec 内存限制: 128 MB
提交: 2 解决: 1
[提交] [状态] [讨论版] [命题人:]题目描述
著名卡牌游戏《石炉传说》中有一张随从牌：恐狼后卫。恐狼后卫的能力是使得相邻随从的攻击力提高。
现在有n张恐狼后卫顺序排成一排，第i只恐狼后卫的攻击力为ai，血量为hi，提升相邻随从的攻击力值为bi。你的攻击力为atk，每次攻击你可以选择一只存活的恐狼后卫，减少其血量值atk。若其血量小于等于0，则该恐狼后卫死亡。当某只恐狼后卫死亡时，其左右两侧（若存在）的恐狼后卫会靠拢并成为相邻关系。在攻击第i只恐狼后卫时，除了要承受这只恐狼后卫自身的攻击力ai之外，还要承受与其相邻的2张恐狼后卫的提高攻击力值bi−1和bi+1（若存在）。
你的任务是承受最少的总伤害杀死所有恐狼后卫，输出需承受的伤害值。
输入
第一行一个正整数n，表示恐狼后卫的数量。
第二行一个正整数atk，表示你的攻击力。
以下n行，每行3个值：ai、bi、hi，分别表示第i只恐狼后卫自身的攻击力值、提升相邻随从的攻击力值、血量值。
输出
一个整数，表示杀死所有恐狼后卫需要承受的最少伤害值。
样例输入
3
1
8 1 6
3 5 7
4 9 2
样例输出
94
提示
对于30%的数据，n≤10
对于另外30%的数据，n≤100,hi=1
对于100%的数据，n≤400,atk,ai,bi,hi≤1000
[提交][状态]