Problem Statement

Maximum Internship Salary An internship lasts N days. On day i , Stephen may complete an easy task for easy[i] , complete a difficult task for hard[i] , or rest for zero pay. A difficult task may be completed only if he rested on the previous day. On day 1, a difficult task is allowed because there is no previous workday. Find the maximum total salary. Input The first line contains N type , where type is always 2. Each of the next N lines contains easy[i] hard[i] . Output Print the maximum salary. Constraints 1 <= N <= 100000 type = 2 1 <= easy[i] < hard[i] <= 10000 Example Input: 3 2 4 10 5 8 4 10 Output: 20 Notes Resting after a difficult task is optional; only the day before a difficult task must be a rest day.