All Tracks>Problem
RELATIVES
★★★★★

3.6

16 votes
Very-Easy
Problem

You own a courier service. It’s Diwali, so you have a lot of packages to send out. To make your problems worse, three of your relatives - A, B and C send you trucks full of packages that they want to send out, and request you to send them out for free. Also, they insist that each of their packages must be sent in the same order in which they arrive at your office. That is, if a package p appears before package q in the ordering of packages, it cannot be placed in a box after q. The two may be placed in the same box. You don’t want to create a scene, so you reluctantly agree.

A sends you a packages, B sends you b packages, C sends you c packages. Each package has some weight w. Your company ships packages in boxes of capacity K. That is, you can put any number of packages in each box as long as the total weight of the box does not exceed K.

Since you wish to conserve boxes, what is the minimum number of boxes that can carry all the packages?

Input
  • First line contains four space separated integers - a, b, c and K.
  • Next line contains a space separated integers - weights of packages of A in order.
  • Next line contains b space separated integers - weights of packages of B in order.
  • Next line contains c space separated integers - weights of packages of C in order.
Output
  • Output a single integer - minimum number of boxes required.
Constraints:
  • 1 ≤ a, b, c ≤ 100
  • 1 ≤ K ≤ 109
  • 1 ≤ w ≤ K

Sample Input
3 3 4 100
98 40 40
2 30 30
20 20 20 100
Sample Output
4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

An optimal way to send the packages is to pack A[1] and B[1] in box 1; A[2], B[2], B[3] in box 2; A[3], C[1], C[2], C[3] in box 3; C[4] in box 4.

Editor Image

?