You cannot submit for this problem because the homework's deadline is due.

Background

Aim to check the correctness of the code.
Here all the provided cases have feasible answer. However, in your submitted algorithm, you need to consider the cases with non existing solution.

Description

See canvas. For submission, you need to submit a zip containing challenge.py.

Format

Input

6 lines in total.
Line 1: number of cities needs to consider \(c\);
Line 2: truck capacity \(s\);
Line 3: total hours of a day \(t\);
Line 4: initial number of packages \(p_i\) at each city \(i\);
Line 5: number of packages \(a_i\) that are added every hour at city \(i\);
Line 6: capacity of the warehouse \(w_i\) at city \(i\).

Output

Minimum number of trucks

Sample 1

Input

3
10
3
2 3 4
4 3 2
10 9 8

Output

2