{"problem":{"name":"Vacation","description":{"content":"Taro's summer vacation starts tomorrow, and he has decided to make plans for it now. The vacation consists of $N$ days. For each $i$ ($1 \\leq i \\leq N$), Taro will choose one of the following activiti","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_c"},"statements":[{"statement_type":"Markdown","content":"Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.\nThe vacation consists of $N$ days. For each $i$ ($1 \\leq i \\leq N$), Taro will choose one of the following activities and do it on the $i$\\-th day:\n\n*   A: Swim in the sea. Gain $a_i$ points of happiness.\n*   B: Catch bugs in the mountains. Gain $b_i$ points of happiness.\n*   C: Do homework at home. Gain $c_i$ points of happiness.\n\nAs Taro gets bored easily, he cannot do the same activities for two or more consecutive days.\nFind the maximum possible total points of happiness that Taro gains.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq a_i, b_i, c_i \\leq 10^4$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$ $c_1$\n$a_2$ $b_2$ $c_2$\n$:$\n$a_N$ $b_N$ $c_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_c","tags":[],"sample_group":[["3\n10 40 70\n20 50 80\n30 60 90","210\n\nIf Taro does activities in the order C, B, C, he will gain $70 + 50 + 90 = 210$ points of happiness."],["1\n100 10 1","100"],["7\n6 7 8\n8 8 3\n2 5 2\n7 8 6\n4 6 8\n2 3 4\n7 5 1","46\n\nTaro should do activities in the order C, A, B, A, C, B, A."]],"created_at":"2026-03-03 11:01:14"}}