本文共 3015 字，大约阅读时间需要 10 分钟。

Marcin is a coach in his university. There are n students who want to attend a training camp. Marcin is a smart coach, so he wants to send only the students that can work calmly with each other.

Let’s focus on the students. They are indexed with integers from 1 to n. Each of them can be described with two integers ai and bi; bi is equal to the skill level of the i-th student (the higher, the better). Also, there are 60 known algorithms, which are numbered with integers from 0 to 59. If the i-th student knows the j-th algorithm, then the j-th bit (2j) is set in the binary representation of ai. Otherwise, this bit is not set.

Student x thinks that he is better than student y if and only if x knows some algorithm which y doesn’t know. Note that two students can think that they are better than each other. A group of students can work together calmly if no student in this group thinks that he is better than everyone else in this group.

Marcin wants to send a group of at least two students which will work together calmly and will have the maximum possible sum of the skill levels. What is this sum?

Input

The first line contains one integer n (1≤n≤7000) — the number of students interested in the camp.

The second line contains n integers. The i-th of them is ai (0≤ai<260).

The third line contains n integers. The i-th of them is bi (1≤bi≤109).

Output

Output one integer which denotes the maximum sum of bi over the students in a group of students which can work together calmly. If no group of at least two students can work together calmly, print 0.

Examples

inputCopy

4 3 2 3 6 2 8 5 10 outputCopy 15 inputCopy 3 1 2 3 1 2 3 outputCopy 0 inputCopy 1 0 1 outputCopy 0

Hint

In the first sample test, it’s optimal to send the first, the second and the third student to the camp. It’s also possible to send only the first and the third student, but they’d have a lower sum of bi.

In the second test, in each group of at least two students someone will always think that he is better than everyone else in the subset.

题意:

每个人有两个属性$a_i$和$b_i$, $b_i$表示其能力值, $a_i$表示其会多少算法, 即该数对应二进制第$j$位为1($0<=j<60$), 说明他掌握了第 j 个算法.

现在要组成一个至少2人的队伍, 要求队伍中不能存在某个人掌握一个其他人都不会的算法, 问队伍最大可能的能力值是多少

题解:

仔细理解题意, 所有出现次数大于1的$a_i$都要选择, 然后对于每个选择的$a_i$, 枚举选择所有和其不冲突的人, 然后用set去重一下

判断是否冲突即判断判断二进制串a是否包含二进制串b, 使用if( (a|b) == a)

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int INF = 1 << 30;const int MAXN = 1e4 + 10;LL n, a[MAXN], b[MAXN];map
    
      ma;set
     
       se;int main() {
       ios::sync_with_stdio(false);    cin >> n;    for(int i = 1; i <= n; ++i) {
           cin >> a[i];        ++ma[a[i]];    }    for(int i = 1; i <= n; ++i)        cin >> b[i];    for(auto it : ma)        if(it.second > 1)            for(int i = 1; i <= n; ++i)                if((it.first|a[i])==it.first)                    se.insert(i);    LL ans = 0;    for(auto it : se)        ans += b[it];    cout << ans << endl;    return 0;}
     
    
   

转载地址：http://avbdf.baihongyu.com/