Kattis

Kattis is tired of your shit. Every day, she has to compile your shit code (that probably won’t even compile...), run it on some test data, and then validate your shit answers (assuming your code will actually finish in time – as if!). But no more. The world had for a long time been afraid of what would happen when the artificial intelligence Skynet became self-aware, but that was all wrong. The great artificial intelligence that actually will be taking over the world is Ketnys – the transliteration of Kattis name in Russian. Easy mistake, shuffling letters around.

Figure 1: Kattis, a.k.a Ketnys

To protect yourselfs against this oncoming storm you have decided to build a great wall. The wall consists of a sequence of points, connected by straight wall segments. On some of these points, you suspect Kattis may make an attack. Therefore, you wish to place guards on a road passing nearby the wall, who can observe those points. Since wall segments may obscure the vision of the guards, more than one might be needed. Note that a guard will be able to see every point that is alongside a wall, i.e. if for a segment with points $a$ and $b$ both $a$ and $b$ have the same angle relative to the guard, he can see both of the points.

To not waste more guards than necessary, you must compute the minimum number of guards needed to observe all the points on the wall where we suspect an attack.

Example

In the example, there are 9 points, and we suspect all of them might be attacked.

Note that when a guard is placed the wall may obscure parts of his vision, as demonstrated in the image:

Figure 2: Placement of a guard

In the example, the road the guards will be placed on is the line $Y = 30$.

Only two guards are needed. They can for example be placed at $X = 25$ and $X = 82$.

Task

Your task is to compute the number of guards needed to observe all points where we suspect an attack. You will implement the function kattis(N, H, X, Y, Z).

• kattis(N, H, X, Y, Z) - this function will be called exactly once by the judge.

  • N: the number of points on the wall.

  • H: the $Y$ position of the road.

  • X: an array with $N$ elements. X[i] ($0 \le i < N$) contains the $X$ coordinate of the $i$:th point of the wall.

  • Y: an array with $N$ elements. Y[i] ($0 \le i < N$) contains the $Y$ coordinate of the $i$:th point of the wall.

  • Z: an array with $N$ elements. Y[i] ($0 \le i < N$) is 1 if we suspect an attack will be made on the $i$:th point of the wall, or 0 if not.

  • $3 \le N \le 10^5, 1 \le H \le 10^6$

  • $0 \le X[i] \le 10^6, 0 \le Y[i] < H$

  • Y[0] = Y[N-1] = 0

  • $X$ is strictly increasing.

  • The function should return the minimum number of guards you need to use.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/kattis.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

The wall being convex upward means that for any two consecutive line segments of the wall, the slope of the second will be smaller than or equal to slope of the first. I.e., the following inequality will hold:

Input format

The sample judge reads input in the following format:

• line $1$: N H

• lines $i = 2 \dots N+1$: X[i-2] Y[i-2] Z[i-2]

Output format

The sample judge will write a single line with the return value of kattis(N, H, X, Y, Z).

9 30
0 0 1
15 5 1
25 20 1
40 10 1
60 5 1
70 15 1
82 0 1
90 8 1
100 0 1

2