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: r1 r2 r3 ... rL. 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 ≤ 108), 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 2N 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

Input

8 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

Output

1

Input

8 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

Output

2

Input

100000000 2 2
88888888 88888888
4 4
4 4
88888888 88888888

Output

1

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)

Apparently, keys can flipped horizontally and/or vertically to fit into different locks.