Chia nhóm

Xem PDF
Tác giả:
BaoJiaoPisu
Dạng bài
Điểm: 600 Thời gian: 1.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho hai dãy \(a\) và \(b\) gồm \(N\) số nguyên, các phần tử của \(b\) đôi một khác nhau. Ta tìm cách chia nhóm các phần tử của \(a\), mỗi nhóm có ít nhất \(2\) phần tử. Trong mỗi nhóm, số điểm đạt được là phần tử \(a_i\) sở hữu \(b_i\) cao thứ hai trong nhóm. Hãy tìm cách chia dãy \(a\) thành các nhóm liên tiếp sao cho đạt được tổng số điểm của các nhóm là cao nhất.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((2\le n\le 3 * 10^5)\) thể hiện số phần tử trong hai dãy \(a\) và \(b\)
  • Dòng thứ hai chứa n số nguyên \(a_1, a_2, a_3, ..., a_n\). \((|a_i|\le 10^9)\)
  • Dòng thứ hai chứa n số nguyên \(b_1, b_2, b_3, ..., b_n\). \((|b_i|\le 10^9)\)

Output

  • Một số nguyên duy nhất là kết quả của bài toán.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N\le 1000\)
  • Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

Test 1

Input 
5
1 2 3 5 4
1 5 3 2 4
Output 
8
Note

Ở test ví dụ \(1\), ta chia các phần tử thành \(2\) nhóm. Nhóm \(1\) gồm các phần tử \([1, 2, 3]\) và nhóm 2 gồm \([5, 4]\). Khi đó số điểm đạt được là \(3 + 5 = 8\).

Test 2

Input 
5
-3 4 -10 2 7
1 4 3 2 5
Output 
4
Note

Ở test ví dụ \(2\), phương án tối ưu nhất là chỉ gồm \(1\) nhóm duy nhất. Khi đó số điểm đạt được là \(4\)

Bình luận