Tập mã có trọng số · canuc80k6104

Có $N$ loại quặng. Loại $i$ có mã phần tử $N u mb e r_{i}$ và sức mạnh $M a g i c_{i}$ . Chọn một số loại quặng để tạo vật phẩm. Lựa chọn hợp lệ khi không tồn tại tập con không rỗng có XOR các mã phần tử bằng $0$ ; sức mạnh nhận được là tổng $M a g i c_{i}$ của các loại đã chọn.

Hãy tìm tổng sức mạnh lớn nhất của một lựa chọn hợp lệ.

Input

Dòng đầu chứa $N$ .
Mỗi trong $N$ dòng tiếp theo chứa mã $N u mb e r_{i}$ và trọng số $M a g i c_{i}$ .

Output

In tổng trọng số lớn nhất của một tập mã độc lập.

Constraints

$1 \leq N \leq 1000$ .
$0 \leq N u mb e r_{i} \leq 1 0^{18}, 0 \leq M a g i c_{i} \leq 1 0^{4}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 18$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Hai mã $3$ và $1$ độc lập và có tổng trọng số $15$ ; mã $2$ thuộc không gian do chúng sinh nên không thể thêm.

Mô hình: Có N loại quặng. Loại i có mã phần tử Number_i và sức mạnh Magic_i. Chọn một số loại quặng để tạo vật phẩm. Lựa chọn hợp lệ khi không tồn tại tập con không rỗng có XOR các mã phần tử bằng 0; sức mạnh nhận được là tổng Magic_i của các loại đã chọn.
Mô hình: Hãy tìm tổng sức mạnh lớn nhất của một lựa chọn hợp lệ.
Thuật toán: Sắp xếp các quặng theo Magic giảm dần. Duyệt theo thứ tự đó; thử chèn Number vào cơ sở. Nếu chèn thành công, lấy quặng và cộng sức mạnh; nếu phụ thuộc thì bỏ.
Thuật toán: Đây là greedy chuẩn trên matroid: ưu tiên phần tử trọng số cao, chỉ từ chối khi nó làm tập mất độc lập.
Chứng minh đúng: Các tập mã độc lập tuyến tính tạo thành một matroid: tập con của tập độc lập vẫn độc lập, và tính trao đổi cơ sở đúng trong không gian vector. Định lý greedy của matroid cho biết duyệt trọng số giảm dần và nhận phần tử nếu vẫn độc lập tạo một cơ sở độc lập có tổng trọng số lớn nhất. Có thể chứng minh bằng trao đổi: tại vị trí đầu tiên greedy chọn g mà nghiệm tối ưu không chọn, thêm g vào nghiệm tối ưu tạo một chu trình tuyến tính; bỏ một phần tử trong chu trình có trọng số không lớn hơn g để giữ độc lập mà không giảm tổng.
Độ phức tạp: Sắp xếp O(N log N), chèn O(N*64), bộ nhớ O(N).