#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 998244353;
int n,m;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

int pw[MAXN],pw1[MAXN];

int main(){
    scanf("%d%d",&n,&m);
    if(m == 1){
        puts("1");
        return 0;
    }
    pw[0] = 1;FOR(i,1,MAXN-1) pw[i] = 1ll*pw[i-1]*m%ha;
    pw1[0] = 1;FOR(i,1,MAXN-1) pw1[i] = 1ll*pw1[i-1]*(m-1)%ha;
    int ans = 0;
    FOR(x,2,m){
        int c = 1;
        FOR(k,2,n-1){
            c = 1ll*c*(m-x)%ha;
            int d = (pw1[k-1]+ha-c)%ha;
            add(ans,1ll*d*(n-k)%ha*pw[n-(k+1)]%ha);
        }
    }
    FOR(i,1,n) add(ans,1ll*pw1[i-1]*pw[n-i+1]%ha);
    printf("%d\n",ans);
    return 0;
}

// 解き直し.
// https://atcoder.jp/contests/arc105/editorial/170
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
LL cW[11], bL[101010], bV[101010];

struct bridge{
    LL l, v; // 長さ, 耐荷重.
    bool operator < (const bridge& rhs) const{
        return (v != rhs.v) ? (v > rhs.v) : (l < rhs.l);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL maxW = 0, minV = 202020202020202020;
    rep(i, N){
        scanf("%lld", &cW[i]);
        maxW = max(maxW, cW[i]);
    }
    priority_queue<bridge> pq;
    rep(i, M){
        LL l, v;
        scanf("%lld %lld", &l, &v);
        minV = min(minV, v);
        pq.push({l, v});
    }
    
    // 2. 橋が崩落するパターンを除外.
    if(maxW > minV){
        puts("-1");
        return 0;
    }
    
    // 3. 橋の耐荷重に対する必要な最小間隔を保存.
    int idx = 0;
    while(!pq.empty()){
        bridge b = pq.top();
        pq.pop();
        // printf("b.l=%lld b.v=%lld\n", b.l, b.v);
        bL[idx + 1] = max(bL[idx], b.l);
        bV[idx + 1] = b.v;
        idx++;
    }
    // rep(i, M + 1) printf("l=%lld v=%lld\n", bL[i], bV[i]);
    
    // 4. ラクダの隊列を全探索.
    vector<int> z(N);
    iota(all(z), 0);
    LL ans = -202020202020202020;
    do{
        // 4-1. ラクダの隊列の重量(累積和).
        LL cWCum[N + 1];
        memset(cWCum, 0LL, sizeof(cWCum));
        rep(i, N) cWCum[i + 1] = cWCum[i] + cW[z[i]];
        // rep(i, N) printf("%d ", z[i]);
        // puts("");
        // rep(i, N + 1) printf("%lld ", cWCum[i]);
        // puts("");
        
        // 4-2. 制約.
        LL x[N][N];
        memset(x, 0LL, sizeof(x));
        rep(i, N){
            repx(j, i + 1, N){
                int at = lower_bound(bV, bV + M + 1, cWCum[j + 1] - cWCum[i]) - bV - 1;
                x[i][j] = max(x[i][j], bL[at]);
                x[j][i] = x[i][j];
            }
        }
        // rep(i, N){
        //     repx(j, i + 1, N) printf("%lld ", x[i][j]);
        //     puts("");
        // }
        
        // 4-3. グラフの最長路の長さは？
        // ex.
        // AtCoder Beginner Contest 022 (C - Blue Bird) を ベース に 実装.
        // https://atcoder.jp/contests/abc022/tasks/abc022_c
        // -> 具体的には, Warshall–Floyd法で, 
        // repx(k, 1, N) repx(i, 1, N) repx(j, 1, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        // とあるものを, i = 0 に 固定するイメージで, 更新する形に変更.
        LL g[N][N], way = 0;
        memset(g, 0LL, sizeof(g));
        repx(i, 1, N){
            rep(j, i + 1){
                g[0][i] = min(g[0][i], g[0][j] - x[i][j]);
                way = min(way, g[0][i]);
                // printf("i=%d j=%d %lld \n", i, j, x[i][j]);
            }
        }
        
        // 4-4. 最長路の長さについて, 最小値を更新.
        ans = max(ans, way);
    }while(next_permutation(all(z)));
    
    // 5. 出力.
    printf("%lld\n", -ans);
    return 0;
    
}