Perun, 궁극기!

많은 학생이 겨울 방학을 생산적으로 보낸다. Vlad는 그렇게 하는 데 매우 능숙해졌다! 그는 이미 사흘 동안, New Year 축하 행사에서 남은 샐러드와 귤로 힘을 내며 Perun이라는 영웅으로 플레이해 자신이 가장 좋아하는 MOBA 게임에서 자신의 레이팅을 조정하고 있다.

Perun에게는 "Thunderwrath"라는 궁극기가 있다. 궁극기를 발동하는 순간, 지도에 있는 각 적(총 n명)은 일회성 효과로 체력을 만큼 잃는다. 또한 이 궁극기에는 제한이 있다. 시각이 정수일 때만 발동할 수 있다. 적을 처치했을 때의 초기 현상금은 이다. 추가로 현상금은 매초 씩 증가한다. 형식적으로, 어떤 t초에 궁극기를 발동하여 그 결과 i-th번째 적을 처치하면(즉, 그 적의 체력이 영 이하로 떨어지면), Vlad는 금 단위를 얻는다.

모든 적은 피해를 받을 수도 있고 치유될 수도 있다. 그렇게 되는 방식은 여러 가지이지만, Vlad는 세부 사항에는 관심이 없다. 그는 n명의 적 각각에 대해 다음을 알고 있다:

• — i-th번째 적의 최대 체력;
• — 적의 초기 체력(0-th번째 초의 체력);
• — i-th번째 적이 초당 재생할 수 있는 체력량.

Vlad가 알고 있는 체력 갱신도 m개 있다:

• — 체력이 갱신된 시각;
• — 체력이 갱신된 적;
• — enemyj의 갱신된 체력.

당연히 Vlad는 자신의 수익을 최대화하려 한다. 필요하다면 적절한 초에 궁극기를 발동하기 위해 몇 년이라도 기다릴 수 있다. 0부터(포함) + ∞까지의 범위에서 궁극기를 한 번 발동했을 때 Vlad가 얻을 수 있는 금의 양이 최대가 되도록 하는 정확한 초(반드시 정수여야 함)를 구하고, 그 양을 출력하라.

첫 번째 줄에 공백으로 구분된 두 정수 n와 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105)가 주어진다.

두 번째 줄에는 세 정수 , , (, )가 주어진다.

이어지는 n개의 각 줄에는 세 정수 , , (, )가 주어진다.

다음 m개의 각 줄에는 세 정수 , , (, , )가 주어진다. 각 적에 대해 매초 난로 변경이 하나를 초과하지 않음이 보장된다. 더 형식적으로, 각각의 a에 대해 b이어서 1 ≤ a, b ≤ m, a ≠ b를 만족한다면, 일 때 이다.

Vlad가 "Thunderwrath"를 정확히 한 번 사용했을 때 얻을 수 있는 금의 최대량을 나타내는 하나의 정수를 출력한다. 이 양이 무한히 커질 수 있다면 -1을 출력한다.

그림에서 각 예제의 시간에 따른 각 적의 체력을 볼 수 있다.

Vlad가 한 명의 적을 처치할 수 있는 구간은 노란색으로 표시되어 있다.

Vlad가 두 명의 적을 처치할 수 있는 구간은 보라색으로 표시되어 있다.

첫 번째 예제에서 Vlad는 50-th번째 초에 궁극기를 발동할 수 있다. 적 2과 3의 체력은 각각 40와 50이므로 죽는다. Vlad는 금 2·(1000 + 50·10) = 3000을 얻는다.

두 번째 예제에서 적 1의 최대 체력은 궁극기가 가하는 피해보다 작다. 따라서 이 적은 언제든 처치할 수 있다. 시간이 지남에 따라 현상금이 50씩 증가하므로, 얻을 수 있는 금의 최대량은 무한하다.