밤양갱

Time limit1sMemory limit1024 MB

Summary

Find the fewest seconds to type 'daldidalgo' N times then 'daldidan', using single-letter appends or pasting a substring already typed.

Level: Medium7 of 10
Topics: String, String matching, Dynamic programming
Solved: No attempts yet

문제

달디달고, 달디달고, 달디단, 밤양갱, 밤양갱

<장기하, 밤양갱, 2024>

Minwoo has been hooked on Bibi's new song "밤양갱" all day. The line "달디달고 달디달고 달디달고... 달디단" keeps looping in his head.

In Minwoo's head, daldidalgo repeats $N$ times. Once the repetition ends, the line finishes with daldidan. For example, when $N=3$ , the line that plays in his head is daldidalgodaldidalgodaldidalgodaldidan.

Minwoo wants to know how fast he can type daldidalgodaldidalgo...daldidan into a computer. Every second, he can choose one of the following two operations.

Choose a lowercase letter from a to z and append it to the end of the text typed so far.
Copy a contiguous substring of the text typed so far and paste it at the end. For example, if the text so far is ajouapcshake, he can copy ajouapcshake or apc, but he cannot copy aashake and paste it.

How many seconds does Minwoo need to type the line from the song?

입력

The first line contains $N$ , the number of times daldidalgo appears in Minwoo's head. $(1\leq N \leq 10^9)$

출력

Print the minimum number of seconds needed to type daldidalgo $N$ times and then daldidan once, when Minwoo performs one of the operations above every second.

Examples1

Example 1
Input
```
2
```
Expected output
```
11
```