Bruce is shifting things from his old home to the new one

Bruce is shifting things from his old home to the new one. He can carry at most 2 objects in one move, provided the sum of the weight of those objects is at most ‘k’. If the sum exceeds 'k', then Bruce will carry only 1 object. No object has a weight greater than 'k'. Return the minimum number of moves he’ll require to shift all the objects.

You’re given an integer array arr of N size, containing the weights of different objects, and an integer k, representing the maximum weight he can carry at a time.

Input format –

    • First line will contain the size of the array, N

    • Next ‘N’ lines will contain N integers denoting array arr.

    • The last line will contain integer k.

note
Constraints
    • 1<=N<=1000

    • 1<=arr[i]<=k<=1000

view_list
Examples
Input:
4

3

2

2

1

3

Output:
3

Explanation:
arr = {3, 2, 2, 1}, k = 3

Move 1 -> carry 3

Move 2 -> carry 2 + 1

Move 3 -> carry 2

Answer -> 3 moves required.