Planting Trees on a Street

You are given a street represented as an array (S) of (m) integers, where each element is either (0) (an empty spot) or (1) (a spot with an existing tree). The task is to determine whether it is possible to plant (n) additional trees along the street so that no two trees are adjacent. In other words, if you plant a tree at position (i), then the positions (i-1) and (i+1) (if they exist) must be empty. This problem requires that you read input from the standard input (stdin) and write the result to the standard output (stdout).

inputFormat

The input consists of three parts:

1. The first line contains an integer (m), the number of spots on the street.
2. The second line contains (m) space-separated integers, each being either 0 or 1, representing the street array.
3. The third line contains an integer (n), the number of trees you need to plant.

outputFormat

Output a single line: print (True) if it is possible to plant (n) trees without any two trees being adjacent; otherwise, print (False).## sample

5
1 0 0 0 1
1

True