We wrote the line breaker in a language of our own.

// ATLAS 금칙분류. 어디서 줄을 끊어도 되는지 가리는 분류기다(break-opportunity classifier, kinsoku).

function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }

// ── 글자류 판정 (char-class predicates over a single code point) ──
function 한글분할문자인가(코드: int) -> bool {
  (코드 >= 4352 && 코드 <= 4607)        // U+1100..U+11FF  한글 자모
  || (코드 >= 12592 && 코드 <= 12687)   // U+3130..U+318F  한글 호환 자모
  || (코드 >= 44032 && 코드 <= 55215)   // U+AC00..U+D7AF  한글 음절
  || (코드 >= 13312 && 코드 <= 19903)   // U+3400..U+4DBF  CJK 확장 A
  || (코드 >= 19968 && 코드 <= 40959)   // U+4E00..U+9FFF  CJK 통합
  || (코드 >= 63744 && 코드 <= 64255)   // U+F900..U+FAFF  CJK 호환
  || 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 65306  // ， 、 。 ； ：
}
function 줄머리금지인가(코드: int) -> bool {
  코드 == 41 || 코드 == 93 || 코드 == 125          // ) ] }
  || 코드 == 12301 || 코드 == 12303 || 코드 == 12299 || 코드 == 12297  // 」 』 》 〉
  || 코드 == 44 || 코드 == 46 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63  // , . ; : ! ?
  || 코드 == 12289 || 코드 == 12290            // 、 。
}
function 줄끝금지인가(코드: int) -> bool {
  코드 == 40 || 코드 == 91 || 코드 == 123          // ( [ {
  || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296  // 「 『 《 〈
}

// ── 클러스터 스칼라 전체/일부 판정 (빈 문자열 -> all=true, any=false, Rust와 일치) ──
function 모두한글분할(텍스트: string) -> bool {
  reduce(텍스트.scalars(), true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))
}
function 모두줄머리금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄머리금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄끝금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))
}

// ── 단어 전체 판정 (single-scalar equality, `matches!` 대응) ──
function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
function 라틴붙임표인가(텍스트: string) -> bool {
  단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)
}
function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }
function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }

// ── 이웃 클러스터 가드 (map_or(true,..) / is_some_and(..)) ──
function 다음은라틴공백아님(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => !라틴공백인가(텍스트)
    case None => true
  }
}
function 다음은줄머리금지없음(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => !일부줄머리금지(텍스트)
    case None => true
  }
}
function 다음은라틴공백(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => 라틴공백인가(텍스트)
    case None => false
  }
}
function 다음은일부줄머리금지(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => 일부줄머리금지(텍스트)
    case None => false
  }
}
function 옵션아스키숫자인가(옵션: Option<string>) -> bool {
  match 옵션 {
    case Some(텍스트) => 아스키숫자인가(텍스트)
    case None => false
  }
}

function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
  쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)
}
function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
  모두줄머리금지(현재) && 다음은라틴공백아님(다음) && !숫자구분자인가(현재, 이전, 다음)
}
function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {
  모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)
}

function 분류(클러스터들: Array<string>) -> string {
  let 개수 = 클러스터들.length
  let mut 출력 = ""
  for i in 0..<개수 {
    let 단위 = 클러스터들[i]
    let 단위끝 = i + 1
    let 이전: Option<string> = if i > 0 { 클러스터들.get(i - 1) } else { None }
    let 다음 = 클러스터들.get(단위끝)
    let 결과: { 종류: string, 내보냄: bool } = match true {
      case _ if 단위끝 == 개수 => { 종류: "forced_end", 내보냄: true }
      case _ if 분할가능라틴공백인가(단위) => { 종류: "latin_space", 내보냄: true }
      case _ if 라틴붙임표인가(단위) => { 종류: "latin_hyphen", 내보냄: true }
      case _ if 닫음부호허용인가(단위, 이전, 다음) => { 종류: "closing_punctuation", 내보냄: true }
      case _ if 한글분할허용인가(단위, 다음) => { 종류: "korean_cluster", 내보냄: true }
      case _ if 다음은라틴공백(다음) || 비분할공백인가(단위) || 다음은일부줄머리금지(다음) => { 종류: "", 내보냄: false }
      case _ => { 종류: "hard_fallback", 내보냄: true }
    }
    if 결과.내보냄 {
      let 종류 = 결과.종류
      출력 = if 출력 == "" { "{단위끝} {종류}" } else { "{출력}\n{단위끝} {종류}" }
    }
  }
  출력
}

print(분류(input().split("\n")))

// ATLAS 나쁨도. 한 줄의 나쁨도를 고정소수로 매기는 명세다(fixed-point line badness).

let R = 100000000   // 1e8 비율 스케일 (ratio scale)
let B = 1000000     // 1e6 나쁨도 스케일 (badness scale)

function 반올림나눗셈(분자: int, 분모: int) -> int {   // round-half-up, 음이 아닌 값만
  let 몫 = 분자 / 분모
  let 나머지 = 분자 % 분모
  if 나머지 >= (분모 + 1) / 2 { 몫 + 1 } else { 몫 }
}
function 절댓값(값: int) -> int { if 값 < 0 { -값 } else { 값 } }

function 나쁨도(너비: int, 목표너비: int, 글자수: int, 공백수: int, 분할종류: string, 마지막인가: bool) -> int {
  let 여유 = 목표너비 - 너비
  let 절대여유 = 절댓값(여유)
  let 원시R = if 절대여유 >= 4 * 목표너비 { 4 * R } else { 절대여유 * R / 목표너비 }
  let 조정상한센티 = if 여유 >= 0 { 100 + 공백수 * 45 } else { 100 + 공백수 * 25 }
  let 비례R = 반올림나눗셈(원시R * 100, 조정상한센티)
  let 제곱 = 비례R * 비례R
  let 몫 = 반올림나눗셈(제곱, R)
  let mut 기본B = 반올림나눗셈(몫 * (1000 * B), R)
  if 마지막인가 {
    기본B = 반올림나눗셈(기본B * 2, 5)
    if 너비 * 100 < 목표너비 * 52 && 글자수 > 0 { 기본B += 500 * B }
  }
  if 여유 < 0 {
    기본B += 20000 * B + 반올림나눗셈(20000 * B * 비례R, R)
  }
  if 분할종류 == "latin_hyphen" { 기본B += 65 * B }
  if 분할종류 == "hard_fallback" { 기본B += 50000 * B }
  if 글자수 <= 2 { 기본B += 275 * B }
  기본B += 10 * B
  기본B
}

function 처리(입력: string) -> string {
  let mut 출력 = ""
  for 줄 in 입력.split("\n") {
    let 칸 = 줄.split("|")
    let 너비 = toInt(칸[0]) ?? 0
    let 목표 = toInt(칸[1]) ?? 0
    let 글자수 = toInt(칸[2]) ?? 0
    let 공백수 = toInt(칸[3]) ?? 0
    let 분할종류 = 칸[4]
    let 마지막인가 = 칸[5] == "1"
    let 값 = 나쁨도(너비, 목표, 글자수, 공백수, 분할종류, 마지막인가)
    출력 = if 출력 == "" { "{값}" } else { "{출력}\n{값}" }
  }
  출력
}

print(처리(input()))

// ATLAS 정렬벌점. 양끝맞춤의 무리함을 고정소수로 매기는 벌점 명세다(Latin + CJK justification penalty).

let B = 1000000
let R = 100000000
let CAP = 25000
function 반올림나눗셈(분자: int, 분모: int) -> int { let 몫 = 분자 / 분모; let 나머지 = 분자 % 분모; if 나머지 >= (분모 + 1) / 2 { 몫 + 1 } else { 몫 } }
function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }
function 낱말공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }
function U0020인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
function CJK정렬문자인가(코드: int) -> bool {
  (코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 13312 && 코드 <= 19903)
  || (코드 >= 19968 && 코드 <= 40959) || (코드 >= 44032 && 코드 <= 55203) || (코드 >= 63744 && 코드 <= 64255)
}
function 정렬부호코드인가(코드: int) -> bool {
  코드 == 46 || 코드 == 44 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 34 || 코드 == 39
  || 코드 == 40 || 코드 == 41 || 코드 == 91 || 코드 == 93 || 코드 == 123 || 코드 == 125
  || 코드 == 12290 || 코드 == 12289 || 코드 == 65292 || 코드 == 65294
  || 코드 == 12300 || 코드 == 12301 || 코드 == 12302 || 코드 == 12303 || 코드 == 12298 || 코드 == 12299 || 코드 == 12296 || 코드 == 12297
}
function 단일CJK인가(텍스트: string) -> bool { 단일스칼라(텍스트) && CJK정렬문자인가(첫코드포인트(텍스트)) }
function 정렬부호단위인가(텍스트: string) -> bool {
  reduce(텍스트.scalars(), false, (발견: bool, 스칼라: string) => 발견 || 정렬부호코드인가(첫코드포인트(스칼라)))
}
function CJK간격후보인가(왼쪽: string, 오른쪽: string) -> bool { 단일CJK인가(왼쪽) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽) }
function 한글공백간격후보인가(왼쪽: string, 공백: string, 오른쪽: string) -> bool {
  단일CJK인가(왼쪽) && 낱말공백인가(공백) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽)
}
function CJK간격수(텍스트들: Array<string>, 시작: int, 끝: int) -> int {
  let mut 간격 = 0
  for i in 시작..<끝 {
    if i + 1 < 끝 && CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 += 1 }
  }
  for i in 시작..<끝 {
    if i + 2 < 끝 && 한글공백간격후보인가(텍스트들[i], 텍스트들[i + 1], 텍스트들[i + 2]) {
      if !CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 += 1 }
      if !CJK간격후보인가(텍스트들[i + 1], 텍스트들[i + 2]) { 간격 += 1 }
    }
  }
  간격
}

function 정렬벌점(진행: Array<int>, 텍스트들: Array<string>, 목표너비: int, 최소간격: int, 비율M: int,
                  최대조정량: int, 최대간격: int, 최대간격비율R: int, 모드: int, 마지막인가: bool) -> int {
  if 마지막인가 { return 0 }
  let 개수 = 텍스트들.length
  let mut 유효 = 개수
  while 유효 > 0 && 낱말공백인가(텍스트들[유효 - 1]) { 유효 -= 1 }
  if 유효 == 0 { return CAP * B }
  if 목표너비 <= 0 { return CAP * B }
  let 원래너비 = reduce(0..<유효, 0, (합: int, i: int) => 합 + 진행[i])
  if 원래너비 * 1000 < 목표너비 * 비율M { return CAP * B }
  let 조정량 = 목표너비 - 원래너비
  if 조정량 <= 1 { return 0 }
  if 조정량 > 최대조정량 { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }
  if 모드 == 0 {
    let 간격 = filter(0..<유효, (i: int) => U0020인가(텍스트들[i])).length
    if 간격 < 최소간격 || 간격 == 0 { return CAP * B }
    let 초과 = 조정량 - 간격 * 최대간격
    if 초과 > 간격 { return CAP * B + 반올림나눗셈(초과 * B, 간격) }
  } else {
    let 간격 = CJK간격수(텍스트들, 0, 유효)
    if 간격 < 최소간격 || 간격 == 0 { return CAP * B }
    // 대표 CJK 진행은 단일 CJK 단위의 합과 개수로 구한다. 개수가 0이거나 진행이 1 이하면 None으로 보아 CAP를 준다.
    let 대표인덱스 = filter(0..<유효, (i: int) => 단일CJK인가(텍스트들[i]))
    let 대표합 = reduce(대표인덱스, 0, (합: int, i: int) => 합 + 진행[i])
    let 대표수 = 대표인덱스.length
    let 불량 = reduce(대표인덱스, false, (발견: bool, i: int) => 발견 || 진행[i] <= 1)
    if 불량 || 대표수 == 0 { return CAP * B }
    let 초과 = 조정량 - 간격 * 최대간격
    let 비율R = 반올림나눗셈(조정량 * 대표수 * R, 간격 * 대표합)
    let 비율초과 = 비율R - 최대간격비율R
    if 초과 > 간격 || 비율초과 > 100000 {
      let 초과항 = if 초과 > 0 { 반올림나눗셈(초과 * B, 간격) } else { 0 }
      let 비율항 = if 비율초과 > 0 { 비율초과 * 100 } else { 0 }
      return CAP * B + 초과항 + 비율항
    }
  }
  0
}

function 처리(입력: string) -> string {
  let 줄들 = 입력.split("\n")
  let 헤더 = 줄들[0].split(" ")
  let 목표너비 = toInt(헤더[0]) ?? 0
  let 최소간격 = toInt(헤더[1]) ?? 0
  let 비율M = toInt(헤더[2]) ?? 0
  let 최대조정량 = toInt(헤더[3]) ?? 0
  let 최대간격 = toInt(헤더[4]) ?? 0
  let 최대간격비율R = toInt(헤더[5]) ?? 0
  let 모드 = toInt(헤더[6]) ?? 0
  let 마지막인가 = (toInt(헤더[7]) ?? 0) != 0
  let mut 진행: Array<int> = []
  let mut 텍스트들: Array<string> = []
  for li in 1..<줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    텍스트들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
  }
  "{정렬벌점(진행, 텍스트들, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 최대간격비율R, 모드, 마지막인가)}"
}

print(처리(input()))

// ATLAS 라틴정렬벌점. 라틴 낱말사이만 다루는 고정소수 정렬 벌점 명세다(LatinWordSpace justification penalty).

let B = 1000000
let CAP = 25000
function 반올림나눗셈(분자: int, 분모: int) -> int { let 몫 = 분자 / 분모; let 나머지 = 분자 % 분모; if 나머지 >= (분모 + 1) / 2 { 몫 + 1 } else { 몫 } }
function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }
function 낱말공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }
function U0020인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }

function 라틴정렬벌점(진행: Array<int>, 텍스트들: Array<string>, 목표너비: int, 최소간격: int,
                      최소라틴비율M: int, 최대조정량: int, 최대간격: int, 마지막인가: bool) -> int {
  if 마지막인가 { return 0 }
  let 개수 = 텍스트들.length
  let mut 유효 = 개수
  while 유효 > 0 && 낱말공백인가(텍스트들[유효 - 1]) { 유효 -= 1 }
  if 유효 == 0 { return CAP * B }
  if 목표너비 <= 0 { return CAP * B }
  let 원래너비 = reduce(0..<유효, 0, (합: int, i: int) => 합 + 진행[i])
  if 원래너비 * 1000 < 목표너비 * 최소라틴비율M { return CAP * B }
  let 조정량 = 목표너비 - 원래너비
  if 조정량 <= 1 { return 0 }
  if 조정량 > 최대조정량 { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }
  let 간격수 = filter(0..<유효, (i: int) => U0020인가(텍스트들[i])).length
  if 간격수 < 최소간격 { return CAP * B }
  let 너비초과분자 = 조정량 - 간격수 * 최대간격
  if 너비초과분자 > 간격수 { return CAP * B + 반올림나눗셈(너비초과분자 * B, 간격수) }
  0
}

function 처리(입력: string) -> string {
  let 줄들 = 입력.split("\n")
  let 헤더 = 줄들[0].split(" ")
  let 목표너비 = toInt(헤더[0]) ?? 0
  let 최소간격 = toInt(헤더[1]) ?? 0
  let 비율M = toInt(헤더[2]) ?? 0
  let 최대조정량 = toInt(헤더[3]) ?? 0
  let 최대간격 = toInt(헤더[4]) ?? 0
  let 마지막인가 = (toInt(헤더[5]) ?? 0) != 0
  let mut 진행: Array<int> = []
  let mut 텍스트들: Array<string> = []
  for li in 1..<줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    텍스트들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
  }
  "{라틴정렬벌점(진행, 텍스트들, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 마지막인가)}"
}

print(처리(input()))

// ATLAS 최적분할. 전체 비용이 가장 낮은 줄 분할을 고르는 고정소수 정수 DP 명세다(optimal-fit integer DP).

let R = 100000000
let B = 1000000

// ── 금칙분류 (ATLAS와 바이트 단위 동일) ──
function 첫코드포인트(텍스트: string) -> int { 텍스트.codePointAt(0) ?? -1 }
function 단일스칼라(텍스트: string) -> bool { 텍스트.scalars().length == 1 }
function 한글분할문자인가(코드: int) -> bool {
  (코드 >= 4352 && 코드 <= 4607) || (코드 >= 12592 && 코드 <= 12687) || (코드 >= 44032 && 코드 <= 55215)
  || (코드 >= 13312 && 코드 <= 19903) || (코드 >= 19968 && 코드 <= 40959) || (코드 >= 63744 && 코드 <= 64255)
  || 코드 == 65292 || 코드 == 12289 || 코드 == 12290 || 코드 == 65307 || 코드 == 65306
}
function 줄머리금지인가(코드: int) -> bool {
  코드 == 41 || 코드 == 93 || 코드 == 125 || 코드 == 12301 || 코드 == 12303 || 코드 == 12299 || 코드 == 12297
  || 코드 == 44 || 코드 == 46 || 코드 == 59 || 코드 == 58 || 코드 == 33 || 코드 == 63 || 코드 == 12289 || 코드 == 12290
}
function 줄끝금지인가(코드: int) -> bool {
  코드 == 40 || 코드 == 91 || 코드 == 123 || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296
}
function 모두한글분할(텍스트: string) -> bool {
  reduce(텍스트.scalars(), true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))
}
function 모두줄머리금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄머리금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄끝금지(텍스트: string) -> bool {
  reduce(텍스트.scalars(), false, (발견: bool, 스칼라: string) => 발견 || 줄끝금지인가(첫코드포인트(스칼라)))
}
function 분할가능라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && 첫코드포인트(텍스트) == 32 }
function 라틴공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 32 || 첫코드포인트(텍스트) == 160) }
function 비분할공백인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 160 || 첫코드포인트(텍스트) == 8239) }
function 라틴붙임표인가(텍스트: string) -> bool {
  단일스칼라(텍스트) && (첫코드포인트(텍스트) == 45 || 첫코드포인트(텍스트) == 8208 || 첫코드포인트(텍스트) == 8209 || 첫코드포인트(텍스트) == 8211)
}
function 쉼표마침표콜론인가(텍스트: string) -> bool { 단일스칼라(텍스트) && (첫코드포인트(텍스트) == 44 || 첫코드포인트(텍스트) == 46 || 첫코드포인트(텍스트) == 58) }
function 아스키숫자인가(텍스트: string) -> bool { 텍스트.byteLength() == 1 && 첫코드포인트(텍스트) >= 48 && 첫코드포인트(텍스트) <= 57 }
function 다음은라틴공백아님(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => !라틴공백인가(텍스트)
    case None => true
  }
}
function 다음은줄머리금지없음(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => !일부줄머리금지(텍스트)
    case None => true
  }
}
function 다음은라틴공백(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => 라틴공백인가(텍스트)
    case None => false
  }
}
function 다음은일부줄머리금지(다음: Option<string>) -> bool {
  match 다음 {
    case Some(텍스트) => 일부줄머리금지(텍스트)
    case None => false
  }
}
function 옵션아스키숫자인가(옵션: Option<string>) -> bool {
  match 옵션 {
    case Some(텍스트) => 아스키숫자인가(텍스트)
    case None => false
  }
}
function 숫자구분자인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
  쉼표마침표콜론인가(현재) && 옵션아스키숫자인가(이전) && 옵션아스키숫자인가(다음)
}
function 닫음부호허용인가(현재: string, 이전: Option<string>, 다음: Option<string>) -> bool {
  모두줄머리금지(현재) && 다음은라틴공백아님(다음) && !숫자구분자인가(현재, 이전, 다음)
}
function 한글분할허용인가(현재: string, 다음: Option<string>) -> bool {
  모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)
}

// ── 나쁨도 (정렬=없음 경로) ──
function 반올림나눗셈(분자: int, 분모: int) -> int { let 몫 = 분자 / 분모; let 나머지 = 분자 % 분모; if 나머지 >= (분모 + 1) / 2 { 몫 + 1 } else { 몫 } }
function 절댓값(값: int) -> int { if 값 < 0 { -값 } else { 값 } }
function 나쁨도(너비: int, 목표너비: int, 글자수: int, 공백수: int, 분할종류: string, 마지막인가: bool) -> int {
  let 여유 = 목표너비 - 너비
  let 절대여유 = 절댓값(여유)
  let 원시R = if 절대여유 >= 4 * 목표너비 { 4 * R } else { 절대여유 * R / 목표너비 }
  let 조정상한센티 = if 여유 >= 0 { 100 + 공백수 * 45 } else { 100 + 공백수 * 25 }
  let 비례R = 반올림나눗셈(원시R * 100, 조정상한센티)
  let 제곱 = 비례R * 비례R
  let 몫 = 반올림나눗셈(제곱, R)
  let mut 기본B = 반올림나눗셈(몫 * (1000 * B), R)
  if 마지막인가 {
    기본B = 반올림나눗셈(기본B * 2, 5)
    if 너비 * 100 < 목표너비 * 52 && 글자수 > 0 { 기본B += 500 * B }
  }
  if 여유 < 0 { 기본B += 20000 * B + 반올림나눗셈(20000 * B * 비례R, R) }
  if 분할종류 == "latin_hyphen" { 기본B += 65 * B }
  if 분할종류 == "hard_fallback" { 기본B += 50000 * B }
  if 글자수 <= 2 { 기본B += 275 * B }
  기본B += 10 * B
  기본B
}

// ── 분할점(단위 + 종류), 인덱스 0에 센티넬 ──
function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {
  let 개수 = 클러스터들.length
  let mut 단위들 = [0]
  let mut 종류들 = ["forced_end"]
  for i in 0..<개수 {
    let 단위 = 클러스터들[i]
    let 단위끝 = i + 1
    let 이전: Option<string> = if i > 0 { 클러스터들.get(i - 1) } else { None }
    let 다음 = 클러스터들.get(단위끝)
    let 결과: { 종류: string, 내보냄: bool } = match true {
      case _ if 단위끝 == 개수 => { 종류: "forced_end", 내보냄: true }
      case _ if 분할가능라틴공백인가(단위) => { 종류: "latin_space", 내보냄: true }
      case _ if 라틴붙임표인가(단위) => { 종류: "latin_hyphen", 내보냄: true }
      case _ if 닫음부호허용인가(단위, 이전, 다음) => { 종류: "closing_punctuation", 내보냄: true }
      case _ if 한글분할허용인가(단위, 다음) => { 종류: "korean_cluster", 내보냄: true }
      case _ if 다음은라틴공백(다음) || 비분할공백인가(단위) || 다음은일부줄머리금지(다음) => { 종류: "", 내보냄: false }
      case _ => { 종류: "hard_fallback", 내보냄: true }
    }
    if 결과.내보냄 { 단위들.push(단위끝); 종류들.push(결과.종류) }
  }
  { 단위들: 단위들, 종류들: 종류들 }
}

function 처리(입력: string) -> string {
  let 줄들 = 입력.split("\n")
  let 목표 = toInt(줄들[0]) ?? 0
  if 목표 <= 0 || 목표 > 23000000000 { return "OUT_OF_BOUNDS" }
  let mut 클러스터들: Array<string> = []
  let mut 진행: Array<int> = []
  for li in 1..<줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    클러스터들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
  }
  let 개수 = 클러스터들.length
  // 접두합
  let mut 너비접두 = [0]
  let mut 글자접두 = [0]
  for i in 0..<개수 {
    너비접두.push(너비접두[i] + 진행[i])
    글자접두.push(글자접두[i] + 클러스터들[i].scalars().length)
  }
  let 분할점 = 분할점생성(클러스터들)
  let 분할점단위 = 분할점.단위들
  let 분할점종류 = 분할점.종류들
  let 분할점수 = 분할점단위.length
  // DP 상태(병렬 배열, endIndex 순으로 push)
  let mut 상태들: Array<{ 있음: bool, 비용: int, 이전: int, 줄나쁨: int }> = [
    { 있음: true, 비용: 0, 이전: 0, 줄나쁨: 0 }
  ]
  for ei in 1..<분할점수 {
    let 끝단위 = 분할점단위[ei]
    let 끝종류 = 분할점종류[ei]
    let 이전시작 = if ei > 80 { ei - 80 } else { 0 }
    let 마지막인가 = 끝단위 == 개수
    let mut 최선 = { 있음: false, 비용: 0, 이전: 0, 줄나쁨: 0 }
    for pi in 이전시작..<ei {
      if 상태들[pi].있음 {
        let 시작 = 분할점단위[pi]
        if 시작 < 끝단위 {
          let 너비 = 너비접두[끝단위] - 너비접두[시작]
          if !(너비 > 목표 + 1 && 끝단위 > 시작 + 1) {
            let 공백수 = filter(시작..<끝단위, (i: int) => 분할가능라틴공백인가(클러스터들[i])).length
            let 줄비용 = 나쁨도(너비, 목표, 글자접두[끝단위] - 글자접두[시작], 공백수, 끝종류, 마지막인가)
            let 후보비용 = 상태들[pi].비용 + 줄비용
            if !최선.있음 || 후보비용 < 최선.비용 {
              최선 = { 있음: true, 비용: 후보비용, 이전: pi, 줄나쁨: 줄비용 }
            }
          }
        }
      }
    }
    상태들.push(최선)
  }
  let 마지막 = 분할점수 - 1
  if !상태들[마지막].있음 { return "NO_PLAN" }
  // 역추적(reversed 수집)
  let mut 역줄들: Array<{ 시작: int, 끝: int, 줄나쁨: int }> = []
  let mut wi = 마지막
  while wi > 0 {
    let 상태 = 상태들[wi]
    역줄들.push({ 시작: 분할점단위[상태.이전], 끝: 분할점단위[wi], 줄나쁨: 상태.줄나쁨 })
    wi = 상태.이전
  }
  let mut 출력 = ""
  let mut 총비용 = 0
  let mut k = 역줄들.length - 1
  while k >= 0 {
    let 줄 = 역줄들[k]
    let 시작 = 줄.시작
    let 끝 = 줄.끝
    let 줄나쁨 = 줄.줄나쁨
    출력 = if 출력 == "" { "{시작} {끝} {줄나쁨}" } else { "{출력}\n{시작} {끝} {줄나쁨}" }
    총비용 += 줄나쁨
    k -= 1
  }
  "{출력}\nTOTAL {총비용}"
}

print(처리(input()))