偷天换日

题目背景

神偷对艺术馆内的名画垂涎欲滴准备大捞一把。

题目描述

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅,就是分为两个走廊。 每个展览厅内都有若干幅画,每副画都有一个价值。经过走廊和偷画都是要耗费时间的。 警察会在 $n$ 秒后到达进口,在不被逮捕的情况下你最多能得到的价值。 ![](https://cdn.luogu.com.cn/upload/pic/2730.png)

输入输出格式

输入格式


第一行一个整数 $n (n \leq 600)$。 第二行若干组整数,对于每组整数 $(t,x)$,$t$ 表示进入这个展览厅或经过走廊要耗费 $t$ 秒的时间,若 $x>0$ 表示走廊通向的展览厅内有 $x$ 幅画。 接下来 $x$ 对整数 $(w,c)$ 表示偷一幅价值为 $w$ 的画需要 $c$ 秒的时间。若 $x=0$ 表示走廊一分为二。$t,c \leq 5;x \leq 30$。 输入是按深度优先给出的。房间和走廊数不超过 $300$ 个。

输出格式


仅一个整数,表示能获得的最大价值。

输入输出样例

输入样例 #1

50 
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4 

输出样例 #1

1500

说明

来源:改编