题目描述

有 $n$ 块需要晾干的布料，以及两条等长的平行晾晒轨道。第 $i$ 块布料的宽度为 $d_i$，可以选择以下一种悬挂方式：挂在任意一条轨道上，占用这条轨道 $d_i$ 的长度，需要 $s_i$ 分钟晾干；或同时搭在两条轨道上，在每条轨道上各占用 $d_i$ 的长度，需要 $f_i$ 分钟晾干。其中 $f_i\le s_i$。

所有布料必须在同一时刻挂好。你可以任意安排它们的位置，但同一条轨道上的布料不能重叠，等待过程中也不能移动布料或改变悬挂方式。

有 $q$ 次相互独立的询问，每次给出每条轨道的长度 $L$。请分别求出从挂好所有布料到全部晾干所需的最短时间；若无法同时挂下所有布料，输出 $-1$。

输入格式

第一行包含两个整数 $n,q$，表示布料数和询问数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $d_i,f_i,s_i$，依次表示第 $i$ 块布料的宽度、搭在双轨上所需的时间和挂在单轨上所需的时间。

接下来 $q$ 行，每行包含一个整数 $L$，表示该次询问中每条轨道的长度。

输出格式

输出 $q$ 行，每行包含一个整数，依次表示对应询问的最短时间，单位为分钟；无法挂下所有布料时输出 $-1$。

样例输入 1

2 3
2 1 5
3 2 7
5
3
2

样例输出 1

2
7
-1

样例 1 解释

当 $L=5$ 时，两块布料都搭在双轨上，$2$ 分钟后全部晾干。当 $L=3$ 时，每条轨道各挂一块，最少需要 $7$ 分钟。当 $L=2$ 时，第二块布料无法挂下。

样例输入 2

1 2
4 3 9
4
3

样例输出 2

3
-1

样例 2 解释

当 $L=4$ 时，将布料搭在双轨上，$3$ 分钟后晾干；当 $L=3$ 时，布料无法挂下。

数据范围与子任务

对于所有测试数据，保证$1\le n\le3\times10^4$，$1\le q\le3\times10^5$，$1\le d_i,L\le3\times10^5$，$1\le f_i\le s_i\le10^9$。

每个子任务内的正式测试全部通过，才获得该子任务的分数。