#10 「 旅行者 」

统计

国家$Y$风景优美,盛产宝石,但交通不发达。可以认为国家$Y$有$n$个地域,用$1\cdots n$编号,不同地域之间有$n-1$条双向道路,任意两个地域之间可以通过修建好的道路互相到达。虽然道路上可以自由通行,地域内却不可以。每个地域内都有$3$种地形:山地,水域,沼泽。每个地域的不同地形都有不同的通行难度。对于一个旅行者来说,他也有$3$个属性值,表示他面对$3$种地形时的应对能力。如果旅行者想要进入某个地域,他的$3$个属性值必须分别大于等于该地域内$3$种地形的通行难度。

旅行者不会重复经过相同的地域。在他经过的任意一个地域里,他都可以买卖宝石。不同地域宝石价格不同,但同一个地域宝石买入卖出的价格相同。同一个地域最多只能做一次交易,也就是只能选择买一颗宝石,卖一颗宝石,或什么都不做。注意旅行者们的背包大小是有限的,最多只能装$K$颗宝石。

现在有$q$个旅行者,你知道他们初始所在的地域(保证他们可以进入各自的初始地域),以及他们的$3$个属性值。你要分别求出每个旅行者最多可以赚多少钱。旅行者一开始没有宝石,但他们的钱可以视为无限的,也就是不会出现买不起的情况。

输入格式

一行三个正整数$n,q,K$。

之后$n-1$行,每行两个正整数,表示$n-1$条道路所连接的两个地域的编号。

之后$n$行,每行四个正整数,表示每个地域的宝石价格和三种地形的通行难度。

之后$q$行,每行四个正整数,表示每个旅行者的初始位置和三个属性值。

输出格式

$q$行,每行一个数,表示每个旅行者最多可以赚多少钱。

样例数据

input

5 2 2
1 2
1 3
2 4
2 5
2 4 1 4
3 3 4 1
5 2 2 4
9 2 3 3
4 3 3 2
3 4 4 4
2 3 4 3

output

7
6

数据规模与约定

$n,q\le 100000$,宝石价格$\le 10000$,通行难度和旅行者的属性值$\le 4$,$K\le4$。

时间限制:1s

空间限制:1GB

Author: 周驿东