빨래 말리기

해리 비버는 호텔을 운영하며, 관광 시즌이 끝날 때까지 남은 $Q$주 동안 매주 일요일 밤에 침대 시트를 빨아야 한다. $j$주차에 그는 방금 세탁한 침대 시트 $N$장을 길이가 각각 $L_j$인 평행한 빨랫줄 두 개에 널어 말리려 한다. 시트는 옆으로 이어서 걸 수 있지만 서로 겹치면 안 된다. 각 시트는 폭이 $d_i$이고 길이가 길어서, 항상 줄 위에서 $d_i$만큼의 길이를 차지하도록 방향을 맞춰 건다. 시트마다 재질이 달라 건조 시간이 크기와 무관하다. $i$번째 시트는 한 줄에만 걸면 $t^{\text{slow}}_i$분이 걸리고, 두 줄에 동시에 걸면 $t^{\text{fast}}_i$분 만에 마른다. 다만 두 줄에 걸친 시트는 다른 줄의 공간도 차지한다. 해리는 일요일에 가능한 한 빨리 자고 싶어 한다. 모든 시트는 세탁 직후 바로 말리기 시작해야 하므로 모두 동시에 널어야 한다. 각 주차의 최소 건조 시간을 구하고, 그 주에 모두 말리는 것이 불가능하면 그 사실을 알려 준다.

첫째 줄에 시트의 수 $N$과 관광 시즌이 끝날 때까지 남은 주의 수 $Q$가 주어진다. 다음 $N$개 줄에는 각각 시트의 폭 $d_i$, 짧은 건조 시간 $t^{\text{fast}}_i$, 긴 건조 시간 $t^{\text{slow}}_i$가 공백으로 구분되어 주어진다. 마지막 $Q$개 줄에는 각 주차의 빨랫줄 길이 $L_j$가 한 줄에 하나씩 주어진다.

$Q$개의 줄을 출력한다. $j$번째 줄에는 $j$주차에 필요한 최소 건조 시간을 출력한다. 그 주에 시트를 모두 말리는 것이 불가능하면 -1을 출력한다. 최소 건조 시간이 일주일의 분 수보다 길더라도 -1로 바꾸지 말고 그 값을 그대로 출력한다.

• $1 \leq N \leq 3 \cdot 10^4$
• $1 \leq Q \leq 3 \cdot 10^5$
• 모든 $1 \leq i \leq N$에 대해 $1 \leq d_i \leq 3 \cdot 10^5$
• 모든 $1 \leq i \leq N$에 대해 $1 \leq t^{\text{fast}}_i \leq t^{\text{slow}}_i \leq 10^9$
• 모든 $1 \leq j \leq Q$에 대해 $1 \leq L_j \leq 3 \cdot 10^5$