#P5354. 开房间
开房间
题目描述
A 和 B 要通过 关。每关有编号 的房间,两人各打开一个房间,且同一关两人所选房间必须不同。第 关打开第 个房间需消耗 点体力。
从第二关起,若某人上一关选择 号房间,这一关选择 号房间,他还需额外消耗 点体力。求两人通过全部关卡的最小总消耗。
输入格式
第一行三个整数 。接下来 行,每行 个整数。第 行第 个整数为 。
输出格式
输出一行一个整数,表示最小总消耗。
样例
3 3 10
2 13 4
4 3 2
16 4 3
28
数据范围
- 的数据满足 。
- 的数据满足 。
- ,,。原 PDF 将 的下界写为 ,现有评测均有至少两个房间。