Cool Desks

The new classroom at Innopolis School needs $n$ two-seat desks.

Desks come in $k$ types, and each type fixes a size. A desk of type $i$ suits students whose height is in the range from $L_i$ to $R_i$ inclusive. Students outside that range find the desk uncomfortable. The discomfort of such a student is the absolute difference between the student's height and the nearest boundary of the desk's range. If the desk suits the student, the discomfort is zero.

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

$m$ groups of students take turns using the classroom. Each group has $2n$ students, and the height of every student is known. The desks are placed in the classroom, and in each group every desk seats exactly two students. Buy $n$ desks and seat the students of each group so that the total discomfort of all students using the classroom is minimal.

The first line 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, the number of desks to buy, and the number of desk types.

Each of the next $k$ lines contains two integers $L_i$ and $R_i$ ($1 \le L_i \le R_i \le 10^9$), the height range suited to desks of type $i$.

Each of the next $m$ lines describes a group. It contains $2n$ integers $h_1, h_2, \ldots, h_{2n}$ ($1 \le h_i \le 10^9$), the heights of the students in that group.

Print $P$, the minimum total discomfort that can be reached by buying desks and seating the students of each group optimally.

In the first example there is only one group. Buy one desk of each type. Seat the students of heights 5 and 10 at the desk of type 1, and the students of heights 40 and 60 at the desk of type 2. Then only the student of height 40 is uncomfortable, with discomfort 10.