题号：NC212563
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小波有一家杂货铺，不同于其它的商店，这家杂货铺只支持以物易物，但是你身上只有货币，不过学习过马克思主义基本原理概论的我们知道货币是一种固定充当一般等价物的特殊商品。所以在小波的店里货币这种商品为第1号商品，现在有n个商品，编号从1到n。店里有一块牌子上面写着可以用a个x号商品可以交换b个y号商品（商品必须是整个售卖），由于牌子大小有限，所以牌子上只有n-1种交换比例。由于小波是一个精明生意人，所以他不会让某种商品出现无法交换的情况。现在你有一个购物清单，问最少需要多少货币，能买下满足你购物清单的货物（可以多买，不可以少买）。
输入描述:
第一行一个数。
接下来n-1行，每行四个数x,y,a,b表示可以用a个x号商品可以交换b个y号商品。
最后一行n-1个数表示购物清单，第i个数表示第i+1种商品需要购买几种
。
输出描述:
一个数，表示最少需要的货币数。