### COCI 2009/2010, Contest #5

## Task KLETVA

As punishment for destroying half of his city with his monster truck, Mirko now has to pay off his dept to society. He works as an assistant for a famous archaeologist. One of his duties include crafting keys for ancient document boxes.

In ancient times document boxes were locked using elaborate mechanisms with interesting locks. Each lock is **L** centimeters long and **W** centimeters wide and consists of three parts, the upper edge, the lower edge and the empty area between them. Both edges can be represented as a sequence of **L nonnegative integers**: r_{1} r_{2} r_{3} ... r_{L}. Each number in sequence represents the width of edge at that point.

The key for each lock is a small clay tab, fitting perfectly in the area between edges. This image shows a 7 cm long, 8 cm wide lock along with thecorresponding key.

The sequence representing the upper edge is [2, 1, 3, 2, 3, 2, 3], and the sequence representing the lower edge is [3, 4, 2, 3, 2, 3, 4]. Mirko noticed that some keys open more than one lock. Making keys is tedious work so Mirko asked you to find out what is the **minimal number** of different keys he needs to make and still be able to open all of the locks.

### Input

First line of input contains three integers, **W** (1 ≤ **W** ≤ 10^{8}), the width of all locks, **L** (1 ≤ **L** ≤ 1000), the length of all locks, and **N** (1 ≤ **N** ≤ 100), the number of different locks.

The next 2**N** lines describe all locks. Each line contains exactly **L** numbers smaller than **W**. Each pair of lines describes one lock. The first line in one pair describes the upper edge, and the second line the lower edge. **There shall always be at least 1 cm of empty space between both edges on all locks.**

### Output

The first and only line of input should contain a single integer, the minimal number of different keys Mirko needs to craft.

### Sample Tests

## Input8 7 2 2 1 3 2 3 2 3 3 4 2 3 2 3 4 3 2 4 3 4 3 4 2 3 1 2 1 2 3 ## Output1 |
## Input8 4 4 3 3 3 3 3 3 3 3 2 2 2 2 4 4 4 4 1 2 3 4 4 3 2 1 1 1 1 1 5 5 5 5 ## Output2 |
## Input100000000 2 2 88888888 88888888 4 4 4 4 88888888 88888888 ## Output1 |

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Jul 02, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

SourSpinachon Jul 07, 2013 - 5:24:58 pm UTC Clarification