#P1054. 【挑战题】餐馆
【挑战题】餐馆
题目描述
一家餐馆里有n个菜品,第个菜品有对应的数量和价格,现在有m个客人要来点菜,第j个客人会给出买份菜品份的需求。 每当客人需要一份编号为菜品时,你需要执行以下操作:
- 给他一份编号为i的菜品,花费为对应菜品的价格
- 如果需要的菜品没有了,那么我们可以给他一份最便宜的还有剩余数量的菜品
- 如果无法继续提供任何菜品,那么当前客户会生气地离开。
如果一个客户在提供完他要求的菜品数量后仍然没有离开,那么该客户的花费将会是他要求的菜品价值之和。
请注意,即使一个客户生气地离开,已经提供的菜品是不可逆的(无法退回到可用菜品里)。
要求你计算每个客户的花费。
输入
第一行两个整数n,m,分别为菜品的种数和客户的数量 接下来一行,包含n个整数,为第1到n种菜品的数量。 再接下来一行,包含n个整数,为第1到第n种菜品每盘的花费。
接下来m行,每行2个整数,为 第个客户所需要的菜品种类和数量。
输出
共m行,为第1到第m个用户的花费。
输入格式
第一行包含两个整数 和 (),分别表示不同种类的食物和顾客数量。
第二行包含 个正整数 (),其中 表示第 种菜品的初始剩余量。
第三行包含 个正整数 (),其中 表示第 种菜品一道菜的成本。
接下来 行描述了 位顾客的订单。第 行包含两个正整数 和 (,),表示第 位顾客订购的食物种类和数量。
输出格式
输出 行,其中第 行输出第 位顾客的消费金额。
样例 #1
样例输入 #1
8 5
8 6 2 1 4 5 7 5
6 3 3 2 6 2 3 2
2 8
1 4
4 7
3 4
6 10
样例输出 #1
22
24
14
10
39
样例 #2
样例输入 #2
6 6
6 6 6 6 6 6
6 66 666 6666 66666 666666
1 6
2 6
3 6
4 6
5 6
6 66
样例输出 #2
36
396
3996
39996
399996
0
样例 #3
样例输入 #3
6 6
6 6 6 6 6 6
6 66 666 6666 66666 666666
1 6
2 13
3 6
4 11
5 6
6 6
样例输出 #3
36
11058
99996
4333326
0
0
提示
在第一个样例中,将为 位客人提供以下服务。
顾客 将被提供 道 号菜肴、 道 号菜肴和 道 号菜肴。费用为 。剩余数量 种食物的数量将为 。
顾客 将被提供 道 号菜肴。费用为 。剩余数量将为 。
顾客 将被提供 道 号菜肴和 道 号菜肴。费用为 。剩余数量将为 。
顾客 将被提供 道 号菜肴和 道 号菜肴。费用为 。剩余数量将为 。
顾客 将被提供 道 号菜肴和 道 号菜肴。费用为 。剩余数量将为 。
在第二个样例中,每位顾客都会得到他们点的菜肴,除了最后一个愤怒离开而不付款。例如,第二位顾客将得到 道第二种菜肴,因此费用为 。
在第三个样例中,有些顾客可能得不到他们点的菜肴。例如,第二位顾客将得到 道第二种菜肴、 道第三种菜肴和 道第四种菜肴,因此费用为 。