The new Innopolis school classroom needs to purchase $n$ two-seater desks.

There are $k$ types of desks, which are defined by their size. A desk of type $i$ is suitable for students whose height is in the range $[L_i, R_i]$ inclusive. It is uncomfortable for other students to sit at such a desk; the discomfort of a student sitting at such a desk is defined as the absolute difference between their height and the nearest boundary of the desk's range. If a desk is suitable for a student, their discomfort is zero.

For example, if $L_i = 100$ and $R_i = 120$, the discomfort for a student with a height of $80$ is $20$, for a student with a height of $130$ it is $10$, and for a student with a height of $105$ it is $0$.

In the classroom, $m$ groups of students will study in turns, each consisting of $2n$ people. The height of each student in each group is known. The purchased desks will be placed in the classroom, and in each group, exactly two students will sit at each desk. It is necessary to purchase $n$ desks and seat the students of each group at them in such a way that the total discomfort for all students studying in this classroom is minimized.

You are required to write a program that, given information about each of the $k$ types of desks and the known heights of each student in each group, determines the minimum total discomfort of the students that can be achieved by purchasing desks and optimally seating the students in each group.

Input

The first line of input contains three integers $m$, $n$, and $k$ ($1 \le m, n \le 200\,000$; $1 \le m \cdot n \le 200\,000$; $2 \le k \le 200\,000$) — the number of groups of students who will study in the classroom, the number of desks that need to be purchased, and the number of desk types, respectively.

Each of the next $k$ lines contains two integers $L_i$ and $R_i$ ($1 \le L_i \le R_i \le 10^9$), characterizing the height range of students for whom desks of type $i$ are suitable.

Each of the next $m$ lines contains a description of a group. Each description consists of $2n$ integers $h_1, h_2, \dots, h_{2n}$, specifying the height of each of the $2n$ students in the group ($1 \le h_i \le 10^9$).

Output

In the only line of output, print $P$ — the minimum total discomfort that can be achieved with an optimal purchase of desks.

Examples

Input 1

1 2 2
5 25
50 90
60 5 10 40

Output 1

10

Input 2

2 3 3
200 400
300 500
100 600
300 330 440 40 30 300
150 250 350 450 550 300

Output 2

130

Input 3

1 3 4
10 100
200 200
10 100
300 1000
5 10 20 15 200 90

Output 3

105

Note

In the first example, there is only one group of students studying in the classroom. One should buy one desk of each type and seat the students with heights $5$ and $10$ at the desk of the first type, and the students with heights $40$ and $60$ at the desk of the second type. In this case, only the student with height $40$ will be uncomfortable, and the corresponding discomfort value will be $10$.