고인물의 두번째 리듬게임

리듬게임 국가대표이자 월드컵 준결승의 주역인 고인물 카루나는 리듬게임을 제패하기 위해 새로운 리듬게임을 시작했다.

카루나가 플레이할 곡은 여러 개의 노트로 이루어져 있다. 각 노트는 곡의 시작으로부터 정확히 $T_i$초 후에 쳐야 하며, 치면 점수 $A_i$와 에너지 $B_i$를 얻는다. 모든 노트에서 얻은 점수의 총합이 최종 점수가 된다. $A_i$가 음수일 수도 있지만, 카루나는 그런 것에 신경 쓰지 않고 항상 모든 노트를 정확한 시간에 친다.

이 게임에는 피버 시스템도 있다. 곡이 시작될 때 피버 게이지는 0이다. 노트를 칠 때마다 그 노트에서 얻은 에너지만큼 피버 게이지가 차오른다. 단, 피버 게이지가 $X$를 초과하면 $X$로 고정된다.

피버 게이지가 $X$만큼 찼을 때, 카루나는 아무 때나 피버 타임을 발동시킬 수 있다. 피버 타임은 정확히 $Y$초 동안 진행되며, 이 동안 처리되는 노트의 점수는 2배가 된다. 피버 타임이 시작되거나 끝나는 순간에 처리되는 노트도 2배의 점수를 얻는다. 피버 타임 동안에는 피버 게이지가 차오르지 않으며, 피버 타임이 끝난 직후 피버 게이지는 0으로 초기화된다.

이 게임에는 여러 난이도가 있고, 난이도마다 최대 피버 게이지 $X$와 피버 타임의 길이 $Y$가 다르다. 각 난이도에서 카루나가 얻을 수 있는 최대 점수를 구해 보자.

첫 줄에 노트의 개수 $N$이 주어진다.

이어지는 $N$개의 줄에는 각 노트의 등장 시각 $T_i$, 점수 $A_i$, 에너지 $B_i$가 주어진다. 모든 $T_i$는 서로 다르다.

다음 줄에는 난이도의 개수 $Q$가 주어진다.

이어지는 $Q$개의 줄에는 각 난이도의 최대 피버 게이지 $X_i$와 피버 타임의 길이 $Y_i$가 주어진다.

$Q$개의 줄에 걸쳐 각 난이도에서 얻을 수 있는 최대 점수를 출력한다.

• $1 \leq N \leq 1,000,000$
• $1 \leq Q \leq 10$
• $0 \leq T_i, B_i \leq 10^9$
• $-10^9 \leq A_i \leq 10^9$
• $1 \leq X_i, Y_i \leq 10^9$
• 입력으로 주어지는 모든 수는 정수이다.