#Pqjdp16. 2.恐狼后卫

2.恐狼后卫

2.恐狼后卫

题目描述

有n张恐狼后卫顺序排成一排,第i只恐狼后卫的攻击力为aia_i,血量为hih_i,提升相邻随从的攻击力值为bib_i。

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

在攻击第i只恐狼后卫时,除了要承受这只恐狼后卫自身的攻击力aia_i之外,还要承受与其相邻的2张恐狼后卫的提高攻击力值bi−1b_{i-1}和  bi+1b_{i+1}(若存在)。

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

输入格式

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

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

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

输出格式

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

数据范围

(原站未提供,导入后需人工补齐)

样例

3
1
8 1 6
3 5 7
4 9 2
94

提示

对于30%的数据,n<=10;

对于另外30%的数据,n<=100,hi=1n<=100,h_i=1;

对于100%的数据,1<=n<=400,atk、ai、bi、hi<=1000a_i、b_i、h_i<=1000。