#B. 土拨鼠大战吐蕃猪

    Type: Default 1000ms 256MiB

土拨鼠大战吐蕃猪

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

魔法师土拨鼠大战愚蠢的人类

题目描述

魔法师土拨鼠芊荨的奶奶被愚蠢的人类抓走了,她一共有 kk 点法力值,一共有 mm 个技能,每个技能耗费的法力值为 aia_i,可以造成的伤害为 bib_i,而 人类 的体力值为 nn,请你求出它放哪个技能,才可以打死 人类。

当然,魔法师土拨鼠芊荨目前的技术很菜,她一局只放一个技能,不过每个技能都可以放无数次。

输入格式

第一行有三个整数,分别表示 k,m,nk,m,n

后面 mm 行,每行两个整数,第 (i+1)(i + 1) 行的整数表示耗费的法力值 aia_i 和造成的伤害 bib_i

输出格式

输出仅一行,既可以杀死 人类 的技能序号,如果有多个,按从小到大的顺序输出,中间用一个空格隔开;如果没有技能能杀死 人类,输出 -1

样例 #1

样例输入 #1

100 3 5000
20 1000
90 1
110 10000

样例输出 #1

1

样例 #2

样例输入 #2

50 4 10
60 100
70 1000
80 1000
90 0

样例输出 #2

-1

提示

数据规模与约定

对于全部的测试点,满足:

  • 0n,m,k3×1040\le n,m,k\le 3\times 10^4,
  • 0ai,bi21474836470 \leq a_i,b_i\le 2147483647

test

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
2
Start at
2023-11-7 10:00
End at
2023-11-7 12:00
Duration
2 hour(s)
Host
Partic.
1