Description

艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。

每个展览厅内都有若干幅画，每副画都有一个价值。经过走廊和偷画都是要耗费时间的。

警察会在 $n$ 秒后到达进口，在不被逮捕的情况下你最多能得到的价值。

Input Format

第一行一个整数 $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$ 个。

Output Format

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

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

1500

Hint

来源：改编