题目内容

$H$餐饮公司为增加销量，以一种主打食物搭配其他若干种小食或饮料，组成一种套餐来销售。例如

$0$:牛肉汉堡+薯条+可乐;

$1$:牛肉汉堡+鸡翅+可乐;

$2$:牛肉饭+鸡翅+牛肉汤

公司为了国庆节的促销活动，提供了如下信息:

$1$.每种套餐的主食$ID$以及套餐成本、利润等信息，表示为[主食$ID$,套餐成本,套餐利润];

$2$.主食是有限制的，表示为[主食$ID$,选择数量上限]，如$100\ 1$，意味着以$100$为主食的套餐仅有一份。

$3$.小食没有限制。

$4$.所有套餐信息，按行描述，套餐从0开始索引。 现在要为公司选出指定数量$NUM$款套餐参加国庆节的促销活动，具体选择策略如下:

1.优先选择成本低的套餐;

2.如果成本相同，则优先选择利润较高的;

3.如果成本相同，利润也相同，则优先选择套餐索引小的;

4.给出限制的主食不能超过其支持的限制数量，没有给出限制的主食不限制数量。

如果能成功选出$NUM$款套餐，则返回它们的套餐索引集合，并按照从小到大排列，否则返回$-1$。

输入描述

第一行一个整数$M$，表示套餐的数量，取值范围[$1,10000$]。

接下来$M$行，每行代表一款套餐，套餐索引从$0$开始，每行三个整数，分别表示主食$ID$，成本，利润。

接下来一行一个整数$N$，表示限制$limit$的数量，取值范围[$1,10000$]。

接下来$N$行，每行两个整数，分别表示主食$ID$，限制数量。

最后一行一个整数$NUM$，表示推出套餐的数量，取值范围[$1,10000$]。

其中主食$ID$，成本，利润，取值范围也都为[$1,10000$]

输出描述

购买的套餐索引，升序排列，如果不能则返回$-1$。

样例1

输入

6
100 30 10
200 10 10
100 50 20
200 10 10
400 20 20
200 20 10
3 
100 1
200 1
400 2
3

输出

0 1 4

说明

公司推出$6$种套餐组合，索引从$0-5$。

按排序规则，优先选择成本为$10$的套餐，利润一样,按索引排序为索引$1$即[$200\ 10\ 10$]，索引$3$即[$200\ 10\ 10$]。

成本$20$的套餐，按利润排序为索引$4$，索引$5$。

成本$30$的套餐，索引$0$。成本$50$的套餐，索引$2$。

最后根据限制条件主食$200、100$的套餐限制为$1$款，输出结果按照套餐索引升序排列$0\ 1\ 4$。

样例2

输入

3
100 30 10 
200 10 10
100 50 20
2
100 1
200 1
3

输出

-1

说明

由于$100,200$的限制都为$1$，所以只能选择两款套餐，数量不足，返回$-1$