Drying Laundry

Harry the Beaver runs a hotel and has to wash bed sheets every Sunday night for the next $Q$ weeks until the tourist season ends. In week $j$, he has $N$ freshly washed bed sheets and wants to dry them by hanging them on two parallel clotheslines, each of length $L_j$. Sheets can hang next to each other but must not overlap. Each sheet is $d_i$ units wide and quite long, so he always hangs it so that it takes up $d_i$ units of a line. The sheets have different drying times because their materials differ, and those times do not depend on their sizes. Sheet $i$ needs $t^{\text{slow}}_i$ minutes when hung on one line. If it is hung over both lines at the same time, it dries in $t^{\text{fast}}_i$ minutes, but it also takes up space on the other line. Harry wants to go to sleep as early as possible on Sundays. All sheets must start drying right after washing, so all of them must be hung at the same time. Find the minimal drying time for each week $j$, or report that the sheets cannot all be dried that week.

The first line contains two integers $N$ and $Q$, the number of sheets and the number of weeks until the end of the tourist season. Each of the next $N$ lines contains three space-separated integers $d_i$, $t^{\text{fast}}_i$, and $t^{\text{slow}}_i$, the width, the shorter drying time, and the longer drying time of sheet $i$. Each of the final $Q$ lines contains one integer $L_j$, the length of the clotheslines in week $j$.

Print $Q$ lines. The $j$-th line contains the minimal required drying time for week $j$, or -1 if it is impossible to finish drying the sheets that week. If the minimal drying time is longer than the number of minutes in a week, print it anyway instead of -1.

• $1 \leq N \leq 3 \cdot 10^4$
• $1 \leq Q \leq 3 \cdot 10^5$
• $1 \leq d_i \leq 3 \cdot 10^5$ for all $1 \leq i \leq N$
• $1 \leq t^{\text{fast}}_i \leq t^{\text{slow}}_i \leq 10^9$ for all $1 \leq i \leq N$
• $1 \leq L_j \leq 3 \cdot 10^5$ for all $1 \leq j \leq Q$