'use strict'
function main(input) {
  input = input.trim().split('\n')
  const N = Number(input.shift())
  const C = input.pop().split(' ')
    .map(v => Number(v)).sort((a, b) => b - a)
  input = input.map(v => v.split(' ').map(w => Number(w)))

  let ans = []
  
  for (let i = 0; i < N; i++) {
    const Ci = C.map(val => [val, -1])
    let Cans = new Array(N).fill([0, -1])
    let M = 0
    input.forEach(side => {
      let l = side[0] - 1
      let r = side[1] - 1
      if (!Cans[l][0]) {
        Cans[l] = [Ci[i][0], i]
        Ci[i][1] = l
      }
      let next = Cans[l][1] + 1
      let inc = true
      while(1) {
        if (next < N && next >= 0) {
          if (Ci[next][1] === -1) {
            Cans[r] = [Ci[next][0], next]
            Ci[next][1] = r
            break
          } else {
            if (inc) {
              next++
            } else {
              next--
            }
          }
        } else {
          next = Cans[l][1] - 1
          inc = false
        }
      }
      M += Math.min(Cans[l][0], Cans[r][0])
    })
    // console.log(i,'回目',[M, Cans.map(arr => arr[0]).join(' ')])
    ans.push([M, Cans.map(arr => arr[0]).join(' ')])
  }
  ans = ans.sort((a, b) => b[0] - a[0])[0]
  console.log(ans[0] + '\n' + ans[1])
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
