Can Place Flowers

You are given an array of integers houses of length n and an integer k. Each element of the array is either 0 or 1, where 0 means the house is empty and 1 means it already has a flower. Your task is to determine whether it is possible to plant k new flowers in these houses without violating the no-adjacent-flowers rule.

The rule is defined as follows: a new flower can be planted in the i-th house if and only if:

\( houses[i] = 0 \) and \( (i = 0 \text{ or } houses[i-1] = 0) \) and \( (i = n-1 \text{ or } houses[i+1] = 0) \).

Output True if it is possible to plant k flowers under the constraint; otherwise, output False.

inputFormat

The first line contains an integer n, the number of houses.

The second line contains n space-separated integers (0 or 1) representing the state of each house.

The third line contains an integer k, the number of flowers to plant.

outputFormat

Output a single line with True if it is possible to plant k new flowers without violating the no-adjacent-flowers rule, otherwise output False.

## sample

5
1 0 0 0 1
1

True

</p>