На праздник пришло \(n\) мальчиков и \(m\) девочек. Каждый мальчик подарил каждой девочке некоторое целое количество конфет (возможно ноль). Пронумеруем мальчиков целыми числами от \(1\) до \(n\) и девочек целыми числами от \(1\) до \(m\). Для всех \(1 \leq i \leq n\) минимальное количество конфет, которое подарил мальчик с номером \(i\) какой-то девочке равно \(b_i\) и для всех \(1 \leq j \leq m\) максимальное количество конфет, которое получила девочка с номером \(j\) от какого-то мальчика равно \(g_j\).
Более формально, Обозначим за \(a_{i,j}\) количество конфет, которое \(i\)-й мальчик подарил \(j\)-й девочке. Тогда \(b_i\) равно минимуму среди значений \(a_{i,1}, a_{i,2}, \ldots, a_{i,m}\) И \(g_j\) равно максимуму среди значений \(b_{1,j}, b_{2,j}, \ldots, b_{n,j}\).
Вам стало интересно, какое минимальное суммарное количество конфет могли подарить мальчики, то есть вы хотите минимизировать сумму \(a_{i,j}\) по всем таким \((i,j)\), что \(1 \leq i \leq n\) и \(1 \leq j \leq m\). По числам \(b_1, \ldots, b_n\) и \(g_1, \ldots, g_m\) определите это число.
Выходные данные
Если не могло быть такой ситуации выведите \(-1\). Иначе выведите минимальное суммарное количество конфет, которое могли подарить мальчики и при этом все условия были бы выполнены.
Примечание
В первом тесте минимальное суммарное количество конфет, которое могли подарить мальчики равно \(12\). Такое могло быть, например, если первый мальчик подарит \(1\) и \(4\) конфеты, второй мальчик подарит \(3\) и \(2\) конфеты и третий мальчик подарит \(1\) и \(1\) конфету первой и второй девочке, соответственно. Легко видеть, что все условия выполнены и суммарно будет подарено \(12\) конфет.
Во втором тесте мальчики не могли подарить конфеты так, чтобы условия были выполнены.
В третьем тесте минимальное суммарное количество конфет, которое могли подарить мальчики равно \(4\). Такое могло быть, например, если первый мальчик подарит \(1\), \(1\), \(2\) конфет первой, второй и третьей девочке, соответственно, а второй мальчик не подарит никому конфет. Легко видеть, что все условия выполнены и суммарно будет подарено \(4\) конфеты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 2 1
3 4
|
12
|
|
2
|
2 2
0 1
1 0
|
-1
|
|
3
|
2 3
1 0
1 1 2
|
4
|