#pragma GCC optimize("Ofast") 
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef int ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
PII e[N];
int cnt=0;
ll ans=-1e9;
ll w[N];
vector<PII> v;
// int cnt[N];


void dfs(int x,int sum,ll val){
    // cout<<x<<" "<<sum<<" "<<val<<endl;
	if(x==0){
        if(val<=ans) return; 
        // cnt+=60*6;
		// cnt++;
        // vector<PII> vv=v;
        // reverse(vv.begin(),vv.end());
        // for(int i=v.size()-1;i>=0;i--){
        //     for(int j=1;j<=v[i].second;j++){
        //         vv.push_back(v[i].first);
        //     }
        // }
        // sort(vv.begin(),vv.end());
        priority_queue<int,vector<int>,greater<int>> q;
        int j=1;
        for(int i=v.size()-1;i>=0;i--){
            // cout<<vv[i]<<" ";
            while(j<=n&&e[j].first<=v[i].first){
                q.push(e[j].second);
                j++;
            }
            while(!q.empty()&&q.top()<v[i].first) q.pop();
            int k=1;
            int need=v[i].first*v[i].second;
            while(k<=need){
                if(q.empty()){
                    // cout<<endl;
                    return;
                } 
                q.pop();
                k++;
            }
        }
        // cout<<endl;
        // cout<<val<<endl;
        ans=max(ans,val);
	}else{
        if(x==1){
            if(n-sum!=0)
            v.push_back({1,n-sum});
            dfs(x-1,n,val+(n-sum)*w[1]);
            
            if(n-sum!=0)
            v.pop_back();
            return;
        }
		for(int i=0;i<=n;i++){
			if(sum+i*x>n) break;
            if(i!=0)
            v.push_back({x,i});
			dfs(x-1,sum+i*x,val+w[x]*i);
            if(i!=0)
            v.pop_back();
        }
	}
}


int main(){
    
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>e[i].first>>e[i].second;
    }
    for(int i=1;i<=n;i++) cin>>w[i];
    sort(e+1,e+1+n);
	dfs(n,0,0);
    // cout<<cnt<<endl;
    if(ans<=-9e8) puts("impossible");
    else
    cout<<ans<<endl;
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<std::pair<int, int>, std::allocator<std::pair<int, int> > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, int>]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~