TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5002
  • 题目
  • P5002「CTSC2018」混合果汁
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 512m
    问题描述

    小 R 热衷于做黑暗料理,尤其是混合果汁。

    商店里有 \(n\) 种果汁,编号为 $0, 1, 2, . . . , n − 1$。\(i\) 号果汁的美味度是 \(d_i\),每升价格为 \(p_i\)。小 R 在制作混合果汁时,还有一些特殊的规定,即在一瓶混合果汁中,\(i\) 号果汁最多只能添加 \(l_i\) 升。

    现在有 \(m\) 个小朋友过来找小 R 要混合果汁喝,他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中,第 \(j\) 个小朋友希望他得到的混合果汁总价格不大于 \(g_j\),体积不小于 \(L_j\)。在上述这些限制条件下,小朋友们还希望混合果汁的美味度尽可能地高,一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

    输入格式

    输入第一行包含两个正整数 \(n, m\),表示果汁的种数和小朋友的数量。接下来 \(n\) 行,每行三个正整数 \(d_i, p_i, l_i\),表示 \(i\) 号果汁的美味度为 \(d_i\),每升价格为$p_i$,在一瓶果汁中的添加上限为 \(l_i\)

    接下来 \(m\) 行依次描述所有小朋友:每行两个数正整数 \(g_j, L_j\) 描述一个小朋友,表示他最多能支付 \(g_j\) 元钱,他想要至少 \(L_j\) 升果汁。

    输出格式

    对于所有小朋友依次输出:对于每个小朋友,输出一行,包含一个整数,表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求,则输出 \(−1\)

    样例输入

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

    样例输出

    3
    2
    -1
    1

    提示

    对于所有的测试数据,保证 \(n, m \le 100000\)

    \(1 \le d_i, p_i, l_i \le 10^5,1 \le g_j, L_j \le 10^{18}\)