Maximum Bananas on Two Pillars

There are two adjacent pillars, A and B. Each pillar has N handles numbered from 1 to N from bottom to top. Each handle on pillar A holds A_i bananas and each handle on pillar B holds B_j bananas (each value is an integer between 0 and 10⁹).

A monkey can grab two handles simultaneously, one on pillar A and one on pillar B, but the two handles must come from different pillars. However, the monkey cannot grab just any pair. There are exactly M allowed pairs. An allowed pair is denoted by \((x, y)\), meaning the monkey can grab the xth handle on pillar A and the yth handle on pillar B at the same time, and then eat all the bananas on those handles. Once bananas are eaten from a handle, they disappear.

The monkey starts at one of the allowed positions. When currently at \((x, y)\), it can move to another allowed pair \((x', y')\) if and only if either:

• \(x < x'\) and \(y = y'\), or
• \(x = x'\) and \(y < y'\).

Note that if a handle has been grabbed (and thus eaten) in an earlier position, grabbing it again will yield no additional bananas. In other words, the monkey collects the bananas on a handle only the first time it appears in the sequence.

Your task is to compute the maximum number of bananas the monkey can eat.

Function Signature

long long int max_bananas(vector<int> A, vector<int> B, vector< pair<int, int> > P)

Here:

• A is an array of length N, where A[i] is the number of bananas on the i+1th handle of pillar A.
• B is an array of length N, where B[i] is the number of bananas on the i+1th handle of pillar B.
• P is an array of M distinct allowed pairs. If \((x, y)\) is in P, then the monkey is allowed to grab handle \(x\) from A and handle \(y\) from B simultaneously.

The monkey can start at any allowed pair, collecting the bananas on both handles. Then, each move adds only the bananas on the newly grabbed handle (if that handle has not been grabbed before). Specifically, if the monkey moves horizontally (i.e. \(x\) increases while \(y\) remains constant) then only the new handle on pillar A contributes, and if it moves vertically, only the new handle on pillar B contributes.

Formally, if the monkey’s sequence is \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\):

• The initial move collects \(A_{x_1}+B_{y_1}\) bananas.
• If \(x_i=x_{i+1}\) (vertical move), then add \(B_{y_{i+1}}\) (provided that handle \(y_{i+1}\) on pillar B has not been used before).
• If \(y_i=y_{i+1}\) (horizontal move), then add \(A_{x_{i+1}}\) (provided that handle \(x_{i+1}\) on pillar A has not been used before).

Output the maximum number of bananas the monkey can eat.

inputFormat

The first line contains two integers N and M.

The second line contains N integers representing array A.

The third line contains N integers representing array B.

Then follow M lines, each containing two integers \(x\) and \(y\) indicating an allowed pair.

outputFormat

Output a single integer, the maximum number of bananas the monkey can eat.

sample

3 3
1 2 3
4 5 6
1 1
2 1
2 2

11