题目描述

Alice 遇上了 $n$ 只妖怪，每只妖怪有一个能力值。Alice 还有 $m$ 张符咒，每张符咒能够消灭一只能力值小于等于 $d$ 的妖怪，由于自身实力等一系列原因，每张符咒有 $c$ 的费用。

现在 Alice 要用最小的费用消灭这 $n$ 只妖怪，请帮她求出最小总费用，若无法消灭，输出 loss。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个正整数 $a_i$ 表示第 $i$ 只妖怪的能力值。

接下来 $m$ 行，每行两个正整数 $d_j,c_j$，表示第 $j$ 张符咒的威力和费用。

输出格式

如果能消灭所有怪物，输出一行一个整数表示最小总费用，否则输出一行 loss。

3 3
1
2
3
2 1
3 2
4 3

6

3 3
2
3
3
2 1
2 2
3 3

loss

数据范围

对于 $10\%$ 的数据，$n\leq10$，$m\leq10$。

对于另外 $20\%$ 的数据，$n\leq5000$​，$m\leq 5000$​。

对于另外 $30\%$ 的数据，$n\leq10^5$​，$m\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$0\leq a_i,d_j,c_j\leq10^6$。