Description

小顾在非洲拥有n座的矿山，有金矿，银矿，铁矿等m种矿山，小顾请了使用最先进的矿山探测技术，探测出这些矿山存储了w_i千克的矿石。因为金融危机，小顾遇到了经济危机，急需y元，因此需要将拥有一些矿山卖出去，因为每一种矿石价格都不一样，帮忙给小顾计算一下，最少需要卖出x个矿山，才能摆脱经济危机。

Input Format

共n+2行

第1行 共3个数，分别为n与m,y 

n表示小顾拥有的矿场数量，m为矿场种类，y需要摆脱经济危机的钱(1<=m<=n<=50000,1<=y<=1000000)

第2行，m个数，按照1-m的矿场种类编号，每种矿石的价格p_i (1<=p_i<=1000000)

接下来n行 每行三个数字分别为id_i,w_i,k_i

id_i为第i个矿山的编号（由5个大小写字母数字组成）, w_i为第i个矿山存储的矿石量,k_i为第i个矿山的矿石种类编号。

(1<=w_i<=1000000，k_i<=m) 

Output Format

共1行，

如果能凑够y，则输出至少卖出的矿山数量x ，

如果不能凑够y，则输出-1

5 4 450
2 5 4 7
A0123 50 1
A0101 30 3
A0221 60 2
B0432 20 4
A0541 90 1

2

Source

贪心