Number of Peanuts

Time limit1sMemory limit128 MB

Summary

Simulate a squirrel that toggles peanuts on a grid while turning left or right, and count the peanuts after t seconds with t up to 1e9.

Level: Medium7 of 10
Topics: Simulation, Implementation, Math
Solved: No attempts yet

Problem

A large old tree stands in the middle of a forest. A squirrel named Darami lives inside a hollow in that tree, and every day she takes a walk through the forest in a very peculiar way.

Darami starts from the old tree facing north, and every second she acts according to the following rules:

If there is a peanut under her feet, she picks it up, turns 90 degrees to the right, and moves forward 1 m.
If there is no peanut under her feet, she puts down one peanut where she stands, turns 90 degrees to the left, and moves forward 1 m.

Darami is so fast that she moves exactly 1 m every second, and so strong that she never runs out of peanuts to carry. Find the number of peanuts lying on the ground after $t$ seconds.

Input

The first line contains the number of peanuts $n$ ( $0 \le n \le 7$ ) lying on the ground at the moment Darami leaves the tree (second 0).

Each of the next $n$ lines contains the position of one peanut as two integers $x$ and $y$ ( $-2 \le x, y \le 2$ ), separated by a space. This means the peanut is located $x$ meters to the east and $y$ meters to the south of the starting point. At most one peanut lies at any single position.

The last line contains the integer $t$ ( $0 \le t \le 10^9$ ), the number of seconds Darami walks.

Output

Print, on the first line, the number of peanuts lying on the ground after $t$ seconds.

Examples4

Example 1
Input
```
2
0 0
-2 1
8
```
Expected output
```
6
```
Example 2
Input
```
0
0
```
Expected output
```
0
```
Example 3
Input
```
0
1
```
Expected output
```
1
```
Example 4
Input
```
0
4
```
Expected output
```
4
```