E79 树上背包 [P3360] 偷天换日
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
P3360 偷天换日(只有样例数据)
题目背景
神偷对艺术馆内的名画垂涎欲滴准备大捞一把。
题目描述
艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。
每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。
警察会在 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。
输入格式
第一行一个整数 。
第二行若干组整数，对于每组整数 ， 表示进入这个展览厅或经过走廊要耗费 秒的时间，若 表示走廊通向的展览厅内有 幅画。
接下来 对整数 表示偷一幅价值为 的画需要 秒的时间。若 表示走廊一分为二。。
输入是按深度优先给出的。房间和走廊数不超过 个。
输出格式
仅一个整数，表示能获得的最大价值。
输入输出样例 #1
输入 #1
50
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4
输出 #1
1500
说明/提示
来源：改编