Submit: 0 Solved: 0

[Submit] [Status] [Web Board] [Creator:]

You want to destroy a bridge with bombs. The lower-left corner of the bridge is at (0,0) and the upper-

right corner is at (w,l). There are already b bombs exploded, the i_th bomb created a hole of radius

r_{i} centering at (x_{i},y_{i}). You want to throw exactly one more bomb so that the bridge is split into two

connected parts(though the two parts can share a finite number of points), so that no one can go through

the bridge from y = 0 to y = l.

Your task is to find the minimal radius of the last bomb to split the bridge, assuming that the last bomb

can explode precisely at the position you want (possibly at non-integer coordinates).

Note that you are only allowed to use bombs with integer radius. That is, even if a bomb with radius

1.01 is su±cient, you have to use a bomb with radius 1, since you only have bombs with integer radius.

The ¯rst line contains t (1<=t<=10), the number of test cases followed. Each test case begins with three

integers w; l; b(1<=w,l<=100; 0<=b<=10). Each of the following b lines contains three integers integers

x_{i},y_{i},r_{i}(0<=x<=w; 0<=y <=l; 0 < r<=100). The bridge is guaranteed to be connected before the last

bomb.

For each test case, print the minimal radius of the last bomb.

```
3
100 100 2
15 50 20
90 50 30
100 100 1
50 50 40
100 100 1
10 50 10
```

```
13
50
40
```