Today, Marisa visited Alice at her house. Alice was busy assigning chores to her collection of $n$ dolls, with $m$ chores in total. She knows that the $i^{th}$ doll can perform the $j^{th}$ chore, as indicated by the $q$ relations she has discovered. A chore can be assigned to only one doll but dolls can be assigned muiltiple chores. The time required to complete a chore is precisely one unit, meaning that if a doll has been assigned $k$ chores, it would take that doll $k$ units of time to finish them all.
However, Alice does not know the minimum units of time needed have all $m$ chores completed. Therefore, she has asked Marisa for help, and Marisa is turning to you for assistance.
### Input
- The first line contains three integers $n,m,q$.
- The next $q$ lines, each line contains two integers $i, j$, the $i^{th}$ doll can do the $j^{th}$ chore.
### Output
- Print the number of minimum units of time needed have all $m$ chores completed. In case there is no way to complete all the chores, print `-1`.
### Constraints
- $1 \le n, m \le 500$.
- $1 \le i \le n$.
- $1 \le j \le m$.
### Example
Input:
```
3 2 4
1 1
1 2
2 1
3 2
```
Output:
```
1
```
**Note: Assign chore 1 to doll 2 and chore 2 to doll 3.**
