#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//typedef tree <int,null_type,less <int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// #include <ext/rope>
// using namespace __gnu_cxx;
typedef long long int ll;
typedef long double ld;
#define FAST                 \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define rep(g, i, n) for (ll g = i; g < n; g++)
#define rev(g, n, i) for (ll g = n - 1; g >= i; g--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define mxe(v) *max_element(v.begin(), v.end())
#define mne(v) *min_element(v.begin(), v.end())
#define ve vector
#define lb lower_bound
#define ub upper_bound
#define bb break
#define cc continue
#define rem 1000000007
#define PI 3.141592653589793238462643383279502
ll power(ll x, ll y, ll p)
{
    ll res = 1; // Initialize result
    x = x % p;  // Update x if it is more than or
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
ll modInverse(ll n, ll p)
{
    return power(n, p - 2, p);
}
struct point
{
    ll x, y;
};
int main()
{
    FAST
        // freopen("input1.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
        /*ll tests;
    cin>>tests;
    rep (gg,0,tests)
    {}*/
        ll n,
        m;
    cin >> n >> m;
    ve<string> arr(n);
    rep(i, 0, n)
    {
        cin >> arr[i];
    }
    ll cnt = 0, ans = 0;
    rep(i, 0, n)
    {
        cnt=0;
        arr[i].pb('#');
        rep(j, 0, m + 1)
        {
            if (arr[i][j] == '.')
            {
                cnt++;
            }
            else if (cnt!=0)
            {
                ans += cnt - 1;
                cnt = 0;
            }
            // cout<<"cnt.. "<<cnt<<"\n";
        }
        arr[i].pop_back();
    }
    rep(j, 0, m)
    {
        cnt=0;
        rep(i, 0, n)
        {
            if (arr[i][j] == '.')
            {
                cnt++;
            }
            else if (cnt!=0)
            {
                ans += cnt - 1;
                cnt = 0;
            }
        }
        if (cnt!=0)
        ans += cnt - 1;
    }
    cout << ans << "\n";
}

#include <bits/stdc++.h>

#define ll long long
using namespace std;
int n,m;
vector<int> w;
vector<tuple<int,int>>brg; // v / l

vector <vector<int>> adjList;

vector <int> segmentTree;


void build(int l, int r,int index){
    if (l==r) segmentTree[index]=get<1>(brg[l]);
    else{
        int mid = l+r >>1;
        build(l,mid,index*2);
        build(mid+1,r,index*2+1);
        segmentTree[index]=max(segmentTree[index*2],segmentTree[index*2+1]);
    }
}

int get (int tl, int tr, int l, int r, int index) {
    if (l>r) return -1;
    if (l==tl && r==tr) return segmentTree[index];
    int mid = tl+tr >>1;
    return max(get(tl,mid,l,min(r,mid),index*2),get(mid+1,tr,max(l,mid+1),r,index*2+1));
}

vector<vector<ll>> dp;

long long getLongest(int f, int t){
    if (dp[t][f]!=-1) return dp[t][f];
    if (t==f) return 0;
    assert(t>f);
    ll re=adjList[t][f];
    int t2=t-1;
    while(t2>f){
        ll tmp1=getLongest(f,t2);
        ll tmp2=getLongest(t2,t);
        ll tmp=tmp1+tmp2;
        if (re<tmp){
            re=tmp;
        }
        t2--;
    }
    return dp[t][f]=re;
}

int main() {
    
    cin>>n>>m;
    w.assign(n,0);
    for (int i=0;i<n;i++){
        cin>>w[i];
    }
    sort(w.begin(),w.end());
        
    brg.assign(m,{0,0});
    for (int i=0;i<m;i++) {
        cin>>(get<1>(brg[i]))>>get<0>(brg[i]);
        if (get<0>(brg[i])<w[0]) {
            cout<<-1<<endl;
            return 0;
        }
    }
    sort(brg.begin(),brg.end());
    
    segmentTree.assign(4*m+1,-1);
    build(0,m-1,1);
    
    long long re =INT_MAX;
    
    adjList.assign(n,vector<int>());
    for (int i=0;i<n;i++){
        adjList[i].assign(i,0);
    }
    do{
        long long retmp=0;
        vector<long long> acu(n+1);
        for (int i=0;i<n;i++) acu[i+1]=acu[i]+w[i];
        // from i to j = acu[j+1]-acu[i]
        
        for (int i=1;i<n;i++){
            for (int j=i-1;j>=0;j--){
                ll wei=acu[i]-acu[j];
                wei+=w[i];
                auto it = upper_bound(brg.begin(),brg.end(),make_tuple(wei,INT_MIN));
                if (it==brg.begin()) {
                    adjList[i][j]=0;
                    continue;
                }
                it--;
                int l=it-brg.begin();
                adjList[i][j]=get(0,m-1,0,l,1);
            }
        }
        
        dp.clear();
        dp.assign(n,vector<ll>(n,-1));

        retmp=getLongest(0,n-1);
        if (re>retmp){
            re=retmp;
        }
    }
    while (next_permutation(w.begin(),w.end()));
    cout<<re<<endl;
    return 0;
}