QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3745. 排列

Statistics

Bobo 有一个长度为 n 的数列 p1,p2,,pnm 个二元组 (a1,b1),(a2,b2),,(am,bm). 他想重新排列数列 p,使得 mi=1|paipbi| 最小。求最小值。

输入格式

输入文件包含多组数据,请处理到文件结束。

每组数据的第一行包含 2 个整数 nm

第二行包含 n 个整数 p1,p2,,pn.

最后 m 行的第 i 行包含 2 个整数 aibi.

输出格式

对于每组数据输出 1 个整数表示所求的最小值。

样例输入

3 2
1 2 5
1 2
2 3
3 3
1 2 5
1 2
1 3
2 3
20 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

样例输出

4
8
0

数据范围

  • 1n20
  • 0mn(n1)2
  • 0pi109
  • 1ai<bin
  • 对于 ij(ai,bi)(aj,bj).
  • 数据组数不超过 5,000,且只有 1 组数据的 n>10.