## Interview Question

**Country:**United States

```
#include<iostream>
#include<vector>
using namespace std;
int main(){
int x,y;
cin>>x>>y;
vector<int> gv(x+1);
vector<int> rv(y+1);
int ans = 0;
int slibings = y + 1;
int mxKid = 0;
for (int g=1 ; g<=x ; ++g) {
cin>>gv[g];
ans+=(gv[g]* slibings);
mxKid+=gv[g];
}
bool isOk= true;
for (int k=1 ; k<=y ; ++k){
cin>>rv[k];
if(rv[k] > mxKid) {
isOk = false;
}
}
```

Looks like Integer linear programming problem to me. I guess the interviewer expects you to use DP here. However an alternative and more fun approach would be to use a specialized tool like z3 in Python where this kind of problems are easy to express:

```
from z3 import *
X = 3
Y = 2
G = [1,2,1]
K = [3,4]
a = [[Int('a_{}_{}'.format(i,j)) for j in range(Y)] for i in range(X)]
s = Optimize()
s.add(And([a[i][j] >= G[i] for i in range(X) for j in range(Y)]))
s.add(And([a[i][j] <= K[j] for i in range(X) for j in range(Y)]))
for j in range(Y):
s.add(Or([a[i][j] == K[j] for i in range(X)]))
for i in range(X):
s.add(Or([a[i][j] == G[i] for j in range(Y)]))
s.minimize(Sum([a[i][j] for i in range(X) for j in range(Y)]))
if s.check() == unsat:
print (-1)
else:
print (simplify(sum([s.model()[a[i][j]] for j in range(Y) for i in range(X)])))
print ([[s.model()[a[i][j]] for j in range(Y)] for i in range(X)])
```

Output:

```
12
[[3, 1], [2, 4], [1, 1]]
```

#include<iostream>

- Anonymous September 06, 2019#include<vector>

using namespace std;

int main(){

int x,y;

cin>>x>>y;

vector<int> gv(x+1);

vector<int> rv(y+1);

int ans = 0;

int slibings = y + 1;

int mxKid = 0;

for (int g=1 ; g<=x ; ++g) {

cin>>gv[g];

ans+=(gv[g]* slibings);

mxKid+=gv[g];

}

bool isOk= true;

for (int k=1 ; k<=y ; ++k){

cin>>rv[k];

if(rv[k] > mxKid) {

isOk = false;

}

}

if (isOk) cout<<ans<<endl; else cout<<-1<<endl;

return 0; }