시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 44 26 22 56.410%

문제

재현이는 여러 액체를 섞어서 음료수를 만드는 취미가 생겼다.

마트에서는 $0, 1, \ldots, n - 1$ 의 번호가 붙어 있는 $n$ 개의 액체를 판다. $i$ 번 액체는 맛이 $d_i$이고, 가격이 1리터당 $p_i$ 이다. 재현이가 만드는 음료수 한 병에는 $i$ 번 액체를 $l_i$ 리터 이하로만 사용해야 한다. (이 수칙을 어길 시에는 건강이 매우 위험해질 수도 있다.)

재현이의 음료를 마시면 건강과 문제 풀이 실력을 맞바꿀 수 있다는 기괴한 소문이 돌면서, $m$ 명의 사람들이 음료수 한 병을 마시기 위해 재현이의 집을 찾아왔다. 이 중 $j$ 번 사람은, 음료수 한 병을 만드는 데 든 액체의 가격이 $g_j$ 이하이며, 양이 $L_j$ 리터 이상이기를 원한다. 이 조건 하에서, $j$ 번 사람은 음료수의 맛을 최대화하고 싶다: 이 때, 음료수의 맛은, 음료수를 이루는 액체들의 맛 중 최솟값이다. 

각 사람에 대해서, 이 사람이 마시게 될 음료수의 맛을 출력하라. 만약 음료수를 대접할 수 없다면, -1을 출력하라.

입력

첫 번째 줄에 두 정수 $n, m$ ($1 \le n, m \le 100\,000$) 이 주어진다.

이후 $n$ 개의 줄에 세 정수 $d_i, p_i, l_i$ 가 주어진다. ($1 \le d_i, p_i, l_i \le 10^5$)

이후 $m$ 개의 줄에 두 정수 $g_i, L_i$ 가 주어진다. ($1 \le g_i, L_i \le 10^{18}$)

출력

$m$ 개의 줄에 정답을 출력하라. $i$ 번째 줄에는 $i$ 번 사람이 마시게 될 음료수의 맛을 출력하라. 만약 음료수를 대접할 수 없다면, -1을 출력하라.

예제 입력 1

3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10

예제 출력 1

3
2
-1
1

예제 입력 2

10 10
71203 70943 96030
2907 3366 43446
59057 58730 29943
20030 19971 5151
54659 54133 16206
61347 60820 58102
73802 73343 32955
49325 49519 51020
53790 53260 12493
60357 60341 33443
1039324449 4656
396371768 1370
1385376577 1519
1468730283 4687
1728094263 8256
124371528 7039
1505613387 3776
1556326425 4864
1231069280 3853
305372610 8028

예제 출력 2

73802
73802
73802
73802
73802
2907
73802
73802
73802
20030

출처

  • 문제를 번역한 사람: koosaga