#include<bits/stdc++.h>
using namespace std;
int n,a[105],ma[105],maxxx[105][105],cnt[105],macnt,maa[105],maxx;
/*
mamxx为到i最优方案
cnt为到i最优方案挖雷次数
macnt为总最优方案挖雷次数
maa为总最优方案
maxx为能挖到最多的地雷数
*/
bool b[105][105];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			cin>>b[i][j];
		}
	}
	for(int i=n;i>=1;i--){
//一定要倒着推，这样才能找到前面走过的路径
		int s=0;
		for(int j=i;j<=n;j++){
			if(b[i][j]==1){//当有通路 
				if(ma[j]>s){
					s=ma[j];
					cnt[i]=cnt[j]; 
					for(int k=1;k<=cnt[j];k++){
						maxxx[i][k]=maxxx[j][k];
					}//转移推出最优方案 
				}
			}
		}
		ma[i]=s+a[i];cnt[i]++;
		maxxx[i][cnt[i]]=i;//把i放入方案 
		if(ma[i]>maxx){
			maxx=ma[i];macnt=cnt[i];
			for(int j=1;j<=macnt;j++) maa[j]=maxxx[i][j];//再推出总最优方案 
		}
	}
	cout<<maxx<<endl;
	for(int i=macnt;i>=1;i--) cout<<maa[i]<<" ";
//因为是倒着推的，所以路径也是反的，因题目要求输出正的方案，所以要反的输出 
	return 0;
}
/*
6
8 14 2 17 9 26
0 0 1 1 0 0
0 1 0 0 0
0 1 0 1
0 0 0
0 1
0
*/

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t,maxn,n,i,j,v[105]={},a[105],b[105][105]={},f[105]={};
  bool x;
  cin>>n;
  for(i=1;i<=n;++i)
  {
  	cin>>a[i];
  	f[i]=a[i];
  }
  for(i=1;i<=n;++i)
  for(j=i;j<=n;++j)
  {
  	cin>>x;
  	b[i][j]=x;
  }
  f[n]=a[n];
  for(i=n-1;i>=1;--i)
  {
  	maxn=0;
  	t=0;
  	for(j=i+1;j<=n;++j)
  	if(b[i][j])
  	{
  	  if(maxn<f[j])
  	  {
  	  	maxn=f[j];
  	  	t=j;
	  }
	}
	v[i]=t;
	f[i]=maxn+a[i];
  }
  maxn=-1;
  t=0;
  for(i=1;i<=n;++i)
  if(maxn<f[i])
  {
  	maxn=f[i];
  	t=i;
  }
  cout<<maxn<<'\n';
  cout<<t;
  while(v[t])
  {
  	t=v[t];
  	cout<<' '<<t;
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Dor(i,a,b) for(int i=a;i>=b;i--)
ll f[201],w[201],c[201];
bool a[201][201];
ll n,x,y,l,k,maxx,x1;
int main(){
	memset(a,false,sizeof(a));
	cin>>n;
	For(i,1,n) cin>>w[i];
	For(i,1,n){
		For(j,i,n) {
			cin >> x1;
			if(x1 == 1) a[i][j]=true;
		}
	}
	f[n]=w[n];
	Dor(i,n-1,1) {
		l=0;k=0;
		For(j,i+1,n)
		  if(a[i][j]&&f[j]>l) l=f[j],k=j;
		  f[i]=l+w[i];
		  c[i]=k;
	}
	k=1;
	For(j,2,n)
	  if(f[j]>f[k]) k=j;
	maxx=f[k];
	cout<<maxx<<"\n";
	cout<<k;
	k=c[k];
	while(k) {
		cout<<" "<<k;
		k=c[k];
	}
	return 0;
}
/*
6
8 14 2 17 9 26
0 0 1 1 0 0
0 1 0 0 0
0 1 0 1
0 0 0
0 1
0*/

#include <bits/stdc++.h> using namespace std; long long n,a[200],b[101][101],dp[200],c[200],d[200][200],maxn,k; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=n-i+1;j++){ cin>>b[i][j+i-1]; } } for(int i=n;i>=1;i--){ dp[i]=a[i]; c[i]=1; d[i][1]=i; for(int j=i+1;j<=n;j++){ if(b[i][j]&&dp[i]<dp[j]+a[i]){ dp[i]=dp[j]+a[i]; c[i]=c[j]+1; for(int m=2;m<=c[j]+1;m++){ d[i][m]=d[j][m-1]; } } } if(maxn<dp[i]){ maxn=dp[i]; k=i; } } cout<<maxn<<endl; for(int i=1;i<=c[k];i++)cout<<d[k][i]<<" "; return 0; }