Bajtazar is planning classes at a dance school. For the new edition of the ballroom dance course, one can sign up without a partner, providing preferences regarding the class schedule. Each participant (both ladies and gentlemen) declares for each of the $t$ available time slots how much they are willing to pay if they are enrolled in it.

Bajtazar's task is to form (mixed) pairs and assign them to time slots in which they will learn to dance so that the school's profit is as large as possible. Each participant can be assigned at most one time slot and can learn to dance in at most one pair. The dance hall is large, so any number of pairs can be enrolled in each of the time slots.

Input

The first line of the input contains three integers $n$, $m$, and $t$ ($1 \le n, m \le 10\,000$, $1 \le t \le 10$), representing the number of ladies and gentlemen signed up for the dance course and the number of available time slots, respectively. The ladies are numbered with natural numbers from $1$ to $n$, and the gentlemen from $n + 1$ to $n + m$.

In the $i$-th of the following $n+m$ lines, there is a sequence of $t$ integers $c_{i,1}, c_{i,2}, \dots, c_{i,t}$ ($1 \le c_{i,j} \le 100\,000$ for $j = 1, 2, \dots, t$). The number $c_{i,j}$ represents the amount that the $i$-th participant is willing to pay if they are enrolled in the $j$-th time slot.

Output

Output a single integer representing the maximum profit from organizing the dance course.

Examples

Input 1

2 3 2
5 1
5 1
1 1
2 2
3 4

Output 1

15

Note

In one of the optimal solutions, pairs $(1, 4)$ and $(2, 5)$ dance in time slot 1.