#1779. 优惠购物

    ID: 1779 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1400来源:qoj.ac数据:公开样例二分答案动态规划

优惠购物

优惠购物

题目描述

标题: 优惠购物 - Problem - QOJ.ac

#7646. 优惠购物

Statistics

The problem was used in the following contests:

小 C 要购买 n 个物品,这些物品有前置关系,必须依次购买(即在购买了第 i 个后才能购买第 i+1 个)。

他初始有 m 张优惠劵和无穷多个金币。每个物品有两个属性,价格 ai 和优惠劵的使用上限 bi(0≤bi≤ai)。

购买一个物品的流程如下:

  • 选择使用 x(0≤x≤bi) 张优惠券,付出 ai−x 个金币和 x 张优惠券。
  • 购买完后可得到 ⌊ai−xc⌋ 张优惠券(即一次购买中,每付出 c 个金币可以得到一张优惠券,c 为给定常数)

小 C 想求出最少花费多少个金币能购买全部物品。

输入格式

本题包含多组数据,第一行包含一个整数 T,表示数据组数。

对于每组数据:

  • 第一行包含三个整数 n,m,c。
  • 第二行包含 n 个整数 a1,a2,...,an 表示每个物品的价格。
  • 第三行包含 n 个整数 b1,b2,...,bn 表示优惠劵的使用上限。

输出格式

对于每组数据输出一行:

  • 第一行输出一个整数,表示最少需要的金币数量。

样例数据

样例 1 输入

4
6 16 2
17 14 13 5 13 4
12 5 5 2 10 2
6 4 2
8 1 20 10 4 10
8 1 15 3 4 6
5 40 7
21 47 7 25 47 
9 26 4 4 39 
5 151 10
86 84 164 158 160
43 42 82 79 80

样例 1 输出

34
34
95
463

样例 2

见下发文件。

子任务

对于所有数据,1≤∑n≤106,1≤m,ai,bi≤109,2≤c≤109。

Subtask 1 (5 pts):1≤T≤5,1≤n≤10,1≤m,∑ai,∑bi≤10

Subtask 2 (10 pts):ai=bi

Subtask 3 (10 pts):1≤∑n≤500,1≤∑m,∑ai,∑bi≤500

Subtask 4 (10 pts):1≤∑n≤6000,1≤∑m,∑ai,∑bi≤6000

Subtask 5 (10 pts):1≤∑n≤6000

Subtask 6 (15 pts):1≤∑n≤2×105,2≤c≤20

Subtask 7 (10 pts):1≤∑n≤1×106,2≤c≤20

Subtask 8 (15 pts):1≤∑n≤2×105

Subtask 9 (15 pts):1≤∑n≤1×106

时间限制:1s

空间限制:2048MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
6 16 2
17 14 13 5 13 4
12 5 5 2 10 2
6 4 2
8 1 20 10 4 10
8 1 15 3 4 6
5 40 7
21 47 7 25 47 
9 26 4 4 39 
5 151 10
86 84 164 158 160
43 42 82 79 80
34
34
95
463