Image Processing

Interview

Time limit1sMemory limit512 MB

Summary

Read an N by M grid of RGB triples, binarize each pixel by whether its average meets threshold T, then count the connected components of 255 pixels under 4-directional adjacency.

Level: Medium4 of 10
Topics: BFS, Graph, Matrix, Implementation
Solved: No attempts yet

Problem

You are given a simple but tedious image processing assignment. Its specification is as follows.

A screen with height $N$ and width $M$ consists of $N \times M$ pixels, and the pixel at $(i, j)$ holds the values of three colors: $R_{i,j}$ (Red), $G_{i,j}$ (Green), and $B_{i,j}$ (Blue). Each color is represented by an integer between 0 and 255.

For every pixel, take the average of the three colors. If it is greater than or equal to the threshold $T$ , set the pixel value to 255; otherwise set it to 0. Store the results as a new screen.

In the new screen, a pixel with value 255 is recognized as an object. If pixels with value 255 are adjacent vertically or horizontally, they are recognized as the same object.

Write a program that determines how many objects are on the screen.

Input

The first line gives the height $N$ and width $M$ of the screen, separated by a space.

From the second line to the $N + 1$ -th line, the values $R_{i,j}$ , $G_{i,j}$ , $B_{i,j}$ of the pixels making up the $i$ -th row are given, separated by spaces, for a total of $M$ pixels.

The last line gives the threshold $T$ .

Output

Print the number of objects on the screen. If there are no objects, print 0.

Constraints

$1 \le N, M \le 1,000$
$0 \le R_{i,j}, G_{i,j}, B_{i,j} \le 255$ , and $R_{i,j}, G_{i,j}, B_{i,j}$ are integers
$0 \le T \le 255$ , and $T$ is an integer

Examples2

Example 1

Input

3 3
255 255 255 100 100 100 255 255 255
100 100 100 255 255 255 100 100 100
255 255 255 100 100 100 255 255 255
101

Expected output

Example 2

Input

2 2
124 150 123 100 100 100
103 103 103 183 5 3
255

Expected output