#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#ifdef NDEBUG
  #define assert(e) if(!(e)){stod("");}
#endif
#ifdef ONLINE_JUDGE
  #define debug(x)
  #define debug2(x,y)
  #define debug3(x,y,z)
#else
  #define debug(x) std::cerr<<#x<<": "<<x<<"\n"
  #define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
  #define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"
#endif

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

void solve() {
  ll n;
  scan(n);
  ll m = 86;
  vll fib(m, 0);
  fib[0] = 1;
  fib[1] = 2;
  FOR (i, 2, m) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  vll cnt(m, 0);
  for (int i = m - 1; i >= 0; --i) {
    if (n >= fib[i]) {
      n -= fib[i];
      cnt[i] = 1;
    }
  }
  assert (n == 0);
  vi ans;
  for (int i = m - 1; i >= 0; i -= 2) {
    if (cnt[i]) {
      ans.push_back(1);
    }
    ans.push_back(4);
    if (cnt[i - 1]) {
      ans.push_back(2);
    }
    ans.push_back(3);
  }
  int sz = ans.size();
  assert (sz <= 130);
  print(sz);
  rep (i, sz) {
    print(ans[i]);
  }
}

int main() {
  solve();
  return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	int n, m;
	int w[8];
	cin >> n >> m;
	rep(i, n)cin >> w[i];
	sort(w, w + n);

	vector<pair<int, int>> tmp, vl;

	rep(i, m) {
		int l, v;
		cin >> l >> v;
		tmp.emplace_back(v, l);

		if (v < w[n - 1]) {
			cout << -1 << endl;
			return 0;
		}
	}
	sort(all(tmp));
	for (auto p : tmp) {
		if (vl.empty() || vl.back().first < p.first && vl.back().second < p.second) {
			vl.push_back(p);
		}
		else if(vl.back().first == p.first && vl.back().second < p.second){
			vl.back().second = p.second;
		}
	}



	int ans = INF;
	do {
		int dist[8][8];
		rep(i, n)rep(j, n)dist[i][j] = 0;

		for (int i = 0; i < n; i++) {
			int s = 0;
			for (int j = i; j < n; j++) {
				s += w[j];

				int idx = lower_bound(all(vl), make_pair(s, 0)) - vl.begin();
				if (idx > 0) {
					dist[i][j] = max(dist[i][j], vl[idx - 1].second);
				}
			}
		}

		int x[8] = {};
		while (1) {
			bool update = false;
			for (int i = 0; i < n; i++) {
				for (int j = i; j < n; j++) {
					if (x[j] - x[i] < dist[i][j]) {
						x[j] = x[i] + dist[i][j];
						update = true;
					}
				}
			}
			if (!update)break;
		}
		ans = min(ans, x[n - 1]);

	} while (next_permutation(w, w + n));



	cout << ans << endl;


	return 0;
}
