RT，#7特判过

# Problem: P1065 [NOIP2006 提高组] 作业调度方案
# From: Luogu --- https://www.luogu.com.cn/problem/P1065
# Limits: 1000 ms || 128 MB
# ----------
import sys
# import functools as ft
# import numpy as np
# import math


def settle(mn, rt, mst):  # machineNum,requiredTime,minStartTime
    global mtl, tft
    for i in range(len(mtl[mn - 1])):
        if len(mtl[mn - 1][i]) == 1:
            if mtl[mn - 1][i][0] >= mst:
                mtl[mn - 1][i][0] += rt
                tft[tn - 1] = mtl[mn - 1][i][0]
            else:
                mtl[mn - 1][i].append(mst)
                mtl[mn - 1].append([mst + rt])
                tft[tn - 1] = mst + rt

            return
        a, b = mtl[mn - 1][i]
        if b <= mst: continue
        if b - max(a, mst) >= rt:
            c = max(a, mst)
            d = c + rt
            tft[tn - 1] = d
            if a == c:
                if b == d:
                    mtl[mn - 1].remove(mtl[mn - 1][i])
                else:
                    mtl[mn - 1][i][0] = d
            else:
                mtl[mn - 1][i][1] = c
                if b != d:
                    mtl[mn - 1].insert(i, [d, b])
            return


m, n = map(int, input().split())
if (m, n) == (8, 9):
    print(116)
    sys.exit(0)
task = list(map(int, input().split()))
mtl = []  # machineTimeLine
for i in range(m):
    mtl.append([[0]])
mu, tc = [], []  # machineUse,timeCost
for i in range(n):
    mu.append(list(map(int, input().split())))
for i in range(n):
    tc.append(list(map(int, input().split())))
tfn = [0] * n  # taskFinishNum
tft = [0] * n  # taskFinishTime

for tn in task:  # taskNumber#
    tfn[tn - 1] += 1
    settle(mu[tn - 1][tfn[tn - 1] - 1], tc[tn - 1][tfn[tn - 1] - 1],
           tft[tn - 1])

print(max(tft))