N = gets.to_i A = gets.split.map(&:to_i) B = gets.split.map(&:to_i) X = gets.split.map(&:to_i) Y = gets.split.map(&:to_i) sum = 0 N.times do |i| sum += A[2 * i] + A[2 * i + 1] + X[i] end dp = Array.new(2 * N + 1, sum) N.times do |i| temp = dp.dup 0.upto(2 * N - 1) do |r_cnt| # dobule red # temp[r_cnt] += dp[r_cnt] # one red one blud if temp[r_cnt + 1] < dp[r_cnt] + (Y[i] - X[i]) + (B[2 * i] - A[2 * i]) temp[r_cnt + 1] = dp[r_cnt] + (Y[i] - X[i]) + (B[2 * i] - A[2 * i]) end # one blue one red if temp[r_cnt + 1] < dp[r_cnt] + (Y[i] - X[i]) + (B[2 * i + 1] - A[2 * i + 1]) temp[r_cnt + 1] = dp[r_cnt] + (Y[i] - X[i]) + (B[2 * i + 1] - A[2 * i + 1]) end # double blue if r_cnt + 2 <= 2 * N && temp[r_cnt + 2] < dp[r_cnt] + (B[2 * i] - A[2 * i]) + (B[2 * i + 1] - A[2 * i + 1]) temp[r_cnt + 2] = dp[r_cnt] + (B[2 * i] - A[2 * i]) + (B[2 * i + 1] - A[2 * i + 1]) end end dp = temp end pp dp.max