In daily practice and exams, we often encounter questions where the examiner provides an example sentence and asks us to write a similar one. This type of question, often called "imitation writing," appears not only in elementary school exams but sometimes in high school entrance exams as well. Many students enjoy these questions because they seem more interesting than others. Imitation sentences often take the form "A__B__C", where A, B, and C are given short phrases consisting of one or more words, and the blank parts need to be filled in by the student. Of course, leaving the blanks empty during an exam is also acceptable.

Due to the internet age, we are no longer limited to imitating the questions set by examiners; we can imitate various sentences and paragraphs found online. On March 26, 2011, a message posted on a blog sparked many imitations.

Imitation writing that spreads widely on the internet, because it has unique features in certain aspects, is mostly named as "So-and-so Style" (or "So-and-so-ti"). Opening Renren or refreshing Weibo, you can also find various styles, such as the "I'm sorry style," the "Explain that he loves you style," etc. Mr. Jin noticed this phenomenon and keenly realized that this is a valuable research topic, so he started researching it, intending to publish a paper.

Because of the need for expression, people sometimes add some decorative words into the originally fixed A, B, and C. This increases the difficulty of identifying whether a sentence or paragraph is an imitation of another.

Mr. Jin is now studying works of a style in the form of "ABC", where A, B, and C are short phrases consisting of several words, and * represents 0 or more words. He found a large number of such works online, but many of them do not conform to the original author's format, which is equivalent to inserting 0 or more words into the standard style.

Since the amount of data is too large, Mr. Jin cannot check them one by one, so he asks for your help to remove the minimum number of words to make it the specified style.

Input

The input file quibble.in contains 4 lines. The first line is a potentially non-standard style work T, and the next three lines represent A, B, and C, respectively.

Output

The output file quibble.out contains only one line, which is a single number: the minimum number of words to remove.

Examples

Input 1

xiang yao yi zhi ai zhe mou wu de hua yi yao guai zhi si lai shuo tai chang le xiang 
yao shi xian yi qie meng xiang de hua yi ren lei zhi sheng lai shuo tai duan le 
yao 
tai chang le yao 
tai duan le

Output 1

2

Note

In the example above, the non-standard style work is: "If you want to love something forever, it is too long to say in terms of a monster's death; if you want to realize all your dreams, it is too short to say in terms of human life."

The standard style is: "wanttoo long wanttoo short".

The modified standard style is: "want always love something, in terms of monster's death too long; want realize all dreams, in terms of human life too short".

Constraints

For 20% of the data, $1 \le |T|, |A|, |B|, |C| \le 10$. For 40% of the data, $1 \le |T|, |A|, |B|, |C| \le 100$. For 70% of the data, $1 \le |T|, |A|, |B|, |C| \le 1000$. For 100% of the data, $1 \le |T|, |A|, |B|, |C| \le 50000$; all word lengths do not exceed 5, and the number of occurrences does not exceed 500; the data guarantees that an answer always exists.