题目背景

uuz 想吃西瓜，让妖梦去西瓜地里采，为了考验他，要他必须在最小的时间内采到指定重量的西瓜。妖梦是个铁憨憨，于是拦下了你，要你告诉他答案，否则就砍了你（你身上没有b，而且是0残机）。

题目描述

西瓜地有 $n$ 个西瓜，第 $i$ 个西瓜重量为 $w_i$，坐标为 $(x_i,y_i)$，每个西瓜的坐标互不相同，且坐标不会是 $(0,0)$。妖梦最初的位置为 $(0,0)$，采完所需西瓜后不返回原点，任意两点间距离为它们的曼哈顿距离，经过 $1$ 的距离需要花费 $1$ 的时间。

共有 $m$ 次询问，对于第 $i$ 次询问，他想知道如何用最小的时间，采到不少于 $k_i$ 重量的西瓜。

uuz吃的很多，别指望暴力能过！

输入格式

输入共 $n+2$ 行。

第 $1$ 行两个整数 $n$ 和 $m$，表示西瓜数量和询问次数。

第 $2$ 行到第 $n+1$ 行，一行四个整数 $w_i$，$x_i$，$y_i$，分别表示第 $i$ 个西瓜的重量以及坐标。

第 $n+2$ 行，共 $m$ 个整数，第 $i$ 个整数为 $k_i$，表示需要采到西瓜的最少重量。

输出格式

输出共 $m$ 行，一行一个整数，表示对于每次询问所求的最小的时间。

样例 #1

样例输入 #1

3 3
3 1 1
4 2 3
6 5 2
3
7
13

样例输出 #1

2
5
9

样例 #2

样例输入 #2

4 3
12 -4 9
9 -2 4
32 13 -4
11 12 9
11
40
58

样例输出 #2

13
29
43

提示

样例 #1 解释

对于第一次询问，到达的坐标依次为 $(0,0)$，$(1,1)$；

对于第二次询问，到达的坐标依次为 $(0,0)$，$(1,1)$，$(2,3)$；

对于第三次询问，到达的坐标依次为 $(0,0)$，$(1,1)$，$(2,3)$，$(5,2)$。

数据范围

本题采用 Subtask 计分方式。

子任务	分值	$n\leqslant$	$m\leqslant$	$k\leqslant$	其他限制
$1$	$20$	$7$	$100$	$10^6$	无
$2$	$80$	$16$	$2 \times10^5$	$10^9$

对于全部的数据，保证 $\left | x \right | \le 1 \times 10^9$，$\left | y \right | \le 1 \times 10^9$，$\sum_{i = 1}^{n}w_i \le 1 \times 10^{18}$。

所有询问均有解。

请注意常数对运行时间的影响。