M. За Орду, но не всем это нравится

Условие классной задачи N с одним изменением: боевой дух воодушевлённого орка $b_i$ может оказаться меньше обычного $a_i$. Некоторые орки в присутствии командира робеют.

Разбиение на отряды устроено так же: отряд — цепочка «командир, его подчинённый, подчинённый подчинённого и так далее», воодушевлены все, кроме командира. Нужно максимизировать суммарный дух.

В первой строке $n$ ($1 \le n \le 2000$). В следующих $n$ строках: $k_i$ и номера подчинённых, каждый строго больше $i$. Сумма $k_i$ не превосходит $10^4$.

В следующей строке $n$ чисел $a_i$ ($1 \le a_i \le 10^9$). В последней строке $n$ чисел $b_i$ ($1 \le b_i \le 10^9$) — здесь $b_i$ может быть как больше $a_i$, так и меньше.

Выведите максимальный суммарный боевой дух.