### Problem Statement

You work in a company that produces measuring devices. The software for each device is stored in reprogrammable memory. To program a device, you must connect it to a personal computer and transmit data to the device's reprogrammable memory through a serial interface. Your task is to make this process as efficient as possible.

You are given two int[]s offset and size. Each corresponding pair of elements in offset and size describes a piece of data that must be transmitted to the device. The i-th piece of data consists of size[i] consecutive bytes that must be written starting at the address in offset[i]. To successfully program a device, you must write every piece of the given data. Memory addresses that are not referenced in this data are not important - so you can write anything to those addresses, or write nothing at all to them.

Data is transmitted from the computer to the device through packets. Each packet can contain a maximum of maxData bytes of consecutive data that will be written to a specified memory address. Return the minimum possible total number of packets required to transmit all of the given data to the device.

### Definition

 Class: ProgrammingDevice Method: minPackets Parameters: int[], int[], int Returns: int Method signature: int minPackets(int[] offset, int[] size, int maxData) (be sure your method is public)

### Notes

-Assume that the reprogrammable memory of the measuring device is infinitely large.

### Constraints

-offset will contain between 1 and 50 elements, inclusive.
-offset and size will contain the same number of elements.
-Each element of offset will be between 0 and 1,000,000,000, inclusive.
-Each element of size will be between 1 and 1,000,000,000, inclusive.
-None of the pieces of data described by offset and size will overlap.
-maxData will be between 1 and 2,000,000,000, inclusive.

### Examples

0)

 `{0, 10, 20, 30}` `{8, 5, 3, 11}` `6`
`Returns: 6`
 Send 15 bytes starting from offset 0 in 3 packets. Only 13 of those 15 bytes are meaningful. There are 2 dummy bytes starting from offset 8. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 6 packets are sent.
1)

 `{0, 10, 20, 30}` `{8, 2, 3, 11}` `6`
`Returns: 5`
 Send 12 bytes starting from offset 0 in 2 packets. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 5 packets are sent.
2)

 `{15, 95}` `{1, 20}` `100`
`Returns: 1`
3)

 `{77, 7777, 777}` `{700, 70000, 7000}` `1`
`Returns: 77700`
4)

 `{0,1000000000}` `{1000000000,1000000000}` `2000000000`
`Returns: 1`
5)

 `{0,1000000000}` `{1000000000,1000000000}` `1`
`Returns: 2000000000`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8212

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10783&pm=8212

gevak

#### Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Greedy