Module: गतिशील प्रोग्रामिंग में पैटर्न

Problem

च्लोए अपने दोस्त को एक पत्र लिखना चाहती है। अक्षर - स्ट्रिंग एस, जिसमें लोअरकेस लैटिन अक्षर होते हैं।
दुर्भाग्य से, जैसे ही च्लोए ने पत्र लिखना शुरू किया, उसने महसूस किया कि यह बहुत लंबा था, और इसे पूरी तरह से लिखने में बहुत लंबा समय लगेगा। इसलिए वह स्वयं स्ट्रिंग के बजाय स्ट्रिंग s का एक संकुचित संस्करण लिखना चाहती है।

स्ट्रिंग s — स्ट्रिंग्स का क्रम c₁, s₁, c₂, s₂,   ..., c_k, s_k, जहां c_i — a_i (अग्रणी शून्य के बिना), और s_i — लोअरकेस लैटिन अक्षरों की कुछ स्ट्रिंग। यदि च्लोए स्ट्रिंग को s₁ ठीक ₁ बार लिखता है, तो s₂ ठीक ₂ बार लिखता है, और इसी तरह पर , यह स्ट्रिंग एस उत्पन्न करेगा।
संपीड़ित संस्करण की लंबाई है |c₁| + |s₁| + |c₂|  +  |s₂|... |c_k| + |s_k|। सभी संकुचित संस्करणों के बीच, च्लोए सबसे कम लंबाई वाले को चुनना चाहता है। कम से कम संभव लंबाई खोजने में च्लोए की मदद करें।

इनपुट:
इनपुट की एकल पंक्ति में एक स्ट्रिंग s है जिसमें लोअरकेस लैटिन अक्षर (1 ≤ |s| ≤ 5000) शामिल हैं।

आउटपुट:
एक पूर्णांक प्रिंट करें — स्ट्रिंग s के कंप्रेस किए गए वर्शन की कम से कम लंबाई.

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट आआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआआ 3 एबकैब 6 सीसीज़ाबाबाब 7

स्पष्टीकरण:
पहले उदाहरण में, क्लो निम्नलिखित संस्करण का चयन करेगी: c₁ — 10, स<उप>1 — ए।
दूसरे उदाहरण में, क्लो निम्न संस्करण का चयन करेगी: c₁ — 1, एस<उप>1 — एबीसीएबी।
तीसरे उदाहरण में, क्लो निम्न संस्करण का चयन करेगी: c₁ — 2, स<उप>1 — सी, सी<उप>2 — 1, स<उप>2 — z, c<उप>3 — 4, स<उप>3 — अब।