lego

#include <iostream>
#include <cstdio>

using namespace std;

int s[25], f[15], f1[15], n1[25], n2[25], gasit, ok, rez1[25], rez2[25];

void read(FILE *fin) {
  char c;
  int i, x, cf;

  fscanf(fin, "%c", &c);
  while(c >= '0' && c <= '9') {
    s[0]++;
    s[s[0]] = c - '0';
    fscanf(fin, "%c", &c);
  }
  for(i = 1; i <= s[0] / 2; i++)
    swap(s[i], s[s[0] - i + 1]);
  while(!feof(fin)) {
    fscanf(fin, "%d %d ", &x, &cf);
    f[cf] += x;
    n1[0] += x;
  }
  n2[0] = n1[0];
}

void print_huge(int a[], FILE *fout) {
  for(int i = a[0]; i >= 1; i--)
    fprintf(fout, "%d", a[i]);
}

int cmp(int a[], int b[]) {
  if(a[0] > b[0])
    return 1;
  if(a[0] < b[0])
    return -1;
  for(int i = a[0]; i >= 1; i--)
    if(a[i] > b[i])
      return 1;
    else if(a[i] < b[i])
      return -1;
  return 0;
}

void solve1() {
  for(int k = n1[0]; k >= 1; k--) {
    int j = 9;
    while(j >= 0 + (k == n1[0]) && !f[j])
      j--;
    n1[k] = j;
    f[j]--;
  }
  n2[0] = 0;
}

void solve2() {
  for(int k = n2[0]; k >= 1; k--) {
    int j = 0 + (k == n2[0]);
    while(j <= 9 && !f[j])
      j++;
    n2[k] = j;
    f[j]--;
  }
  n1[0] = 0;
}

void set1(int k) {
  if(k >= 1) {
    if(!ok) {
      if(!gasit && f[s[k]]) {
        n1[k] = s[k];
        f[s[k]]--;
        set1(k - 1);
        f[s[k]]++;
      }
      if(!gasit) { /// cautam cea mai mare cf mai mica decat s[k]
        int j = s[k] - 1;
        while(j >= 0 + (k == n1[0]) && !f[j])
          j--;
        if(j >= 0 + (k == n1[0])) {
          n1[k] = j;
          f[j]--;
          ok = 1;
          set1(k - 1);
          f[j]++;
          ok = 0;
        }
      }
    }
    else {
      int j = 9;
      while(j >= 0 + (k == n1[0]) && !f[j])
        j--;
      if(j >= 0 + (k == n1[0])) {
        n1[k] = j;
        f[j]--;
        set1(k - 1);
        f[j]++;
      }
    }
  }
  else {
    int x = cmp(n1, s);
    if(x == -1)
      gasit = 1;
  }
}

void set2(int k) {
  if(k >= 1) {
    if(!ok) {
      if(!gasit && f1[s[k]]) {
        n2[k] = s[k];
        f1[s[k]]--;
        set2(k - 1);
        f1[s[k]]++;
      }
      if(!gasit) { /// cautam cea mai mare cf mai mica decat s[k]
        int j = s[k] + 1;
        while(j <= 9 && !f1[j])
          j++;
        if(j <= 9) {
          n2[k] = j;
          f1[j]--;
          ok = 1;
          set2(k - 1);
          f1[j]++;
          ok = 0;
        }
      }
    }
    else {
      int j = 0 + (k == n2[0]);
      while(j <= 9 && !f1[j])
        j++;
      if(j <= 9) {
        n2[k] = j;
        f1[j]--;
        set2(k - 1);
        f1[j]++;
      }
    }
  }
  else {
    int x = cmp(n2, s);
    if(x == 1)
      gasit = 1;
  }
}

void subtract(int a[], int b[], int c[]) {/// c = a - b
  for(int i = b[0] + 1; i <= a[0]; i++)
    b[i] = 0;
  b[0] = a[0];
  c[0] = a[0];
  int r = 0;
  for(int i = 1; i <= a[0]; i++) {
    c[i] = a[i] - b[i] - r;
    if(c[i] < 0) {
      r = 1;
      c[i] += 10;
    }
    else
      r = 0;
  }
  while(c[c[0]] == 0)
    c[0]--;
}

int main() {
  FILE *fin = fopen("lego.in", "r");
  FILE *fout = fopen("lego.out", "w");
  int cr, i;

  fscanf(fin, "%d ", &cr);
  read(fin);
  if(n1[0] < s[0])
    solve1();
  else if(n1[0] > s[0])
    solve2();
  else {
    gasit = ok = 0;
    for(i = 0; i <= 9; i++)
      f1[i] = f[i];
    set1(n1[0]);
    if(!gasit)
      n1[0] = 0;
    gasit = ok = 0;
    set2(n2[0]);
    if(!gasit)
      n2[0] = 0;
  }
  if(cr == 1) {
    if(n1[0] == 0)
      fprintf(fout, "0 ");
    else
      print_huge(n1, fout);
    fprintf(fout, " ");
    if(n2[0] == 0)
      fprintf(fout, "0");
    else
      print_huge(n2, fout);
  }
  else {
    if(n1[0] != 0)
      subtract(s, n1, rez1);
    else
      rez1[0] = 0;
    if(n2[0] != 0)
      subtract(n2, s, rez2);
    else
      rez2[0] = 0;
    if(n1[0] == 0)
      if(n2[0] == 0)
        fprintf(fout, "0");
      else
        print_huge(rez2, fout);
    else
      if(n2[0] == 0)
        print_huge(rez1, fout);
      else {
        int x = cmp(rez1, rez2);
        if(x <= 0)
          print_huge(rez1, fout);
        else
          print_huge(rez2, fout);
      }
  }

  return 0;
}