问题 24708. -- 【2014赛前模拟五】支付宝

24708: 【2014赛前模拟五】支付宝

时间限制: 5 Sec  内存限制: 256 MB
献花: 7  解决: 0
[献花][花圈]

题目描述

1.支付宝

(pay.pas/c/cpp)

题目描述

做完前七次Nescafé 模拟赛之后,你已经欠了一大笔电费。现在收电费的已经把你堵在了家里。当然了,你并不是打算一直拖欠电费的人,你只是如果不能用最少的纸币张数凑出电费金额的话会感到十分不爽。本来这是一件很简单的事,但是你平常很少使用标准的纸币,而是习惯去银行领一本支票簿,在每一张上填上自己喜欢的金额然后把这些东西用作纸币付账,这就使问题变得复杂了起来。现在你知道你一共填写了N种金额的支票,第i 种支票的金额和数目分别是Wi Ci,而电费的总额是K。为了尽快把收电费的打发走,你需要写一个程序,帮助你确定使用支票数目最少的支付方案。

输入格式

第一行是一个整数N,表示支票金额的种类数。

第二行是 N 个整数W1, W2, ..., WN,表示支票的金额。

第三行是 N 个整数C1, C2, ..., CN,表示支票的数目。

第四行是一个整数 K,表示电费的金额。

输出格式

第一行输出一个整数 T,表示至少需要使用的支票数目。

第二行按顺序输出 N 个整数U1, U2, ..., UN。其中Ui 表示使用第i 种支票的数目。

//如果有多种方案,你只需要输出任意一个。

//提交时暂不输出方案,但必须掌握。

样例输入

3

2 3 5

2 2 1

10

样例输出

3

//1 1 1

数据范围与约定

对于20% 的数据,N10Wi≤500Ci≤200K2000

对于 100% 的数据,N200Wi, Ci, K20000

 

输入

输出

提示

来源

[献花][花圈]