남우는 어버이날을 맞이하여 요리를 진행하려고 합니다. 요리는 2개를 만들려고 하고, 이를 위해 n 개의 재료를 준비했습니다.

재료를 1번부터 순서대로 n 번까지 나열했다 했을 때, 요리를 만들기 위해서는 다음 두 조건을 만족해야 합니다.

1. 요리는 연속한 재료들로만 만들 수 있습니다. 이때 최소 1개 이상의 재료를 선택해야만 합니다.

2. 서로 다른 요리에 사용되는 재료끼리 겹쳐서도, 그리고 인접해서도 안됩니다.

예로 [재료1, 재료2, 재료3, 재료4, 재료5] 이렇게 5개의 재료가 순서대로 주어졌을 때, ([재료2, 재료3]), ([재료4, 재료5]) 이렇게 재료를 선택하여 두 요리를 만들게 된다면 인접한 재료인 재료3, 재료4는 서로 다른 요리에 사용되므로 불가능한 선택지가 됩니다.

각 재료마다 부모님의 선호도가 정해져 있으며, 만족도는 두 요리에 쓰인 재료의 선호도의 총 합으로 정해집니다. 조건을 만족하며 두 요리를 통해 얻을 수 있는 최대 만족도를 구하는 프로그램을 작성해보세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.