Description

Sam暑假找了个搬砖的活儿，每天12个小时内有1～8种转可以搬，每种的时间的工资都不一样（如搬第一种砖的时间为0时～4时，工资为5元，搬第二种砖的时间为2时～6时，工资为8元），每次搬砖必须搬完才能搬下一次转（即不可重叠，如上例中搬第一种砖就不能搬第二种转），请你帮Sam拿拿主意，怎样安排可以赚到最多的工资？

Input Format

输入包含八组（八种砖），每组包含三个整数：搬砖开始时间s1、结束时间s2与工资sal。(0 <= s1 < 11 , 0 < s2 <= 11 , 1 <= sal <= 10)。

Output Format

Sam12小时内最多可以赚到的工资。

3 5 1
1 4 5
0 6 8
4 7 4
3 8 6
5 9 3
6 10 2
8 11 4​

13​

Source

动态规划