Caramel Clouds

Sweetland의 화단을 가장 잘 장식하는 것은 바닐라 머핀이라는 사실이 잘 알려져 있다. 이 식물의 묘목은 자라기 위해 햇빛이 필요하다. 슬라스티오나에게는 묘목이 m개 있으며, j-th 묘목이 자라려면 적어도 kj분 동안 햇빛을 받아야 한다.

Sweetland는 대부분의 시간 동안 맑지만, 때때로 캐러멜 구름이 나타난다. 그중 i-th 구름은 시각(분) li에 나타나 시각 ri에 사라진다. 물론 구름은 그림자를 만들며, 해를 가리는 구름이 적어도 하나 있으면 묘목은 자랄 수 없다.

슬라스티오나는 자신의 머핀을 가능한 한 빨리 키우고 싶다. 그녀에게는 Sweetland의 주요 화폐인 사탕이 정확히 C개 있다.

사탕 ci개를 지불하면 어떤 구름이든 없앨 수 있다. 하지만 Sweetland's Department of Meteorology 규정을 준수하기 위해 두 개를 초과하는 구름을 없앨 수는 없다.

슬라스티오나는 m개의 묘목 중 어느 것이 공주의 정원에 심어질지 아직 정하지 않았으므로, 여러분의 도움이 필요하다. 각 묘목에 대해 슬라스티오나가 법을 어기지 않고 자신이 가진 것보다 많은 사탕을 쓰지 않을 때 그 묘목이 자랄 수 있는 가장 이른 시각을 구한다. 각 묘목은 독립적으로 고려한다는 점에 유의한다.

묘목은 시각 0부터 자라기 시작한다.

첫 번째 줄에는 두 정수 n와 C (0 ≤ n ≤ 3·105, 0 ≤ C ≤ 109)가 주어진다. 이는 캐러멜 구름의 수와 슬라스티오나가 가진 사탕의 수이다.

다음 n개의 줄에는 각각 세 정수 li, ri, ci (0 ≤ li < ri ≤ 109, 0 ≤ ci ≤ 109)가 주어지며, 각각 하나의 캐러멜 구름을 나타낸다.

다음 줄에는 묘목의 수를 나타내는 정수 하나 m (1 ≤ m ≤ 3·105)가 주어진다. 각 묘목은 필요한 햇빛의 분 수를 나타내는 정수 하나 kj (1 ≤ kj ≤ 109)로 설명된다.

각 묘목에 대해 슬라스티오나가 그 묘목을 키울 수 있는 최소 시각을 분 단위의 정수 하나로 출력한다.

첫 번째 예제를 살펴보자. 각 k에 대해 구름 1과 3을 없애는 것이 최적이다. 그러면 남은 구름은 시간 구간 $[1..6]$에 그림자를 만든다. 따라서 구간 $[0..1]$와 [6..inf)는 맑다.

두 번째 예제에서 k = 1일 때는 아무것도 없앨 필요가 없으며, k = 5일 때 최선의 전략은 구름 2와 3을 없애는 것이다. 이렇게 하면 추가로 맑은 구간 $[4..8]$이 생기며, 이 구간과 $[0..1]$을 함께 이용하면 여덟 번째 분에 머핀을 키울 수 있다.

세 번째 예제에서는 두 묘목이 완전히 다르다. 첫 번째 묘목의 경우 구름 1을 없애서 맑은 구간 $[0..10]$을 얻어야 한다. 하지만 같은 전략을 두 번째 묘목에 적용하면 답은 180이 된다. 대신 구름 2를 없애 구간 $[0..3]$와 [7..inf)를 맑게 만들 수 있으며, 이를 통해 시간을 104로 단축할 수 있다.