有一个无穷大的二维格子。每个格子用一个坐标$(x, y)$表示。在这个二维格子上的方向定义是：上北下南，左东右西。有一只小强初始在$(0, 0)$位置，面向北，每次可以有三种操作：

• -2：表示左转90度；例如从方向北左转90度，就变成了方向西；从方向南左转90度就变成了方向东。
• -1：表示右转90度；例如从方向北右转90度，就变成了方向东；从方向东右转90度就变成了方向南。
• $p$ ($p$是一个自然数)：表示沿着当前方向向前$p$步，例如：当前位置为$(0, 0)$，方向为北，向前一步变为$(0, 1)$；当前位置为$(2, 3)$，方向为西，向前3步变为$(-1, 3)$。

但是在这个二维格子上，有一些格子上面有障碍物，如果小强向前行走的过程中遇到障碍物，他不会进入障碍物所在的格子，并且停留在进入障碍物格子之前的格子。例如当前位置为$(0, 0), p = 5$，方向为北，且$(0, 3)$格子上有障碍物，那么他这次行走后的最终位置是：$(0, 2)$。

给出$n$步操作和$m$个障碍物格子的位置，你能回答出小强在行走过程中距离原点$(0, 0)$的最大距离的平方是多少吗？

数据输入

第一行两个数字$n$和$m$，分别表示$n$步操作和$m$个障碍物格子。 第二行是$n$个整数$A[i]$, $A[i]$是-1或者-2或者一个自然数，表示第$i$步的操作。 第三行到第$m + 2$行，每行两个整数$(x[i], y[i])$，表示第$i$个障碍物格子的位置。

数据输出

一个整数，表示小强在行走过程中距离原点$(0, 0)$的最大距离的平方。

样例输入1

3 0

4 -1 3

样例输出1

25

样例输入2

5 1

4 -1 4 -2 4

2 4

样例输出2

65

范围说明

对于20%的数据有：$1leq nleq 100, m = 0, -2 leq A[i] leq 100, -100leq x[i], y[i] leq 100$。

对于40%的数据有：$1leq nleq 100, 0leq mleq 100, -2 leq A[i] leq 100, -100leq x[i], y[i] leq 100$。

对于100%的数据有：$1leq nleq 10^5, 0leq mleq 10^5, -2 leq A[i]leq 10^9, -10^9leq x[i], y[i] leq 10^9$。