The line-breaker, published in full.

// ATLAS 줄바꿈 — 한국어 식별자 Topaz 줄바꿈기 (the published Korean line-breaker).
//
// 이 모듈은 ATLAS 본문 조판의 줄바꿈 알고리즘 전체를 Topaz로 구현한 것이다.
//   금칙분류(break-opportunity classifier / kinsoku) + 나쁨도(fixed-point badness)
//   + 정렬벌점(justification penalty, Latin + CJK) + 최적분할(optimal-fit integer DP).
// 모든 연산은 정수 밀리포인트(mpt)와 정수 B-단위로 수행한다 — 부동소수 없음.
// 동작은 ATLAS Rust 고정소수 플래너와 바이트 단위로 동일하다(식별자는 의미를 바꾸지 않는다).
//
// This file is the Korean-identifier source of the ATLAS line-breaker, implemented in Topaz.
// It is byte-identical to the proven English PoC (classify/badness/just/dp) and to the
// ATLAS B5 fixed-point Rust planner. Identifiers carry no semantics, so renaming preserves output.
//
// 입력/출력 프로토콜(스텝퍼 — input() → 처리 → print()):
//   입력 0행 헤더: "<목표너비mpt> <첫줄목표너비mpt> <드롭캡줄수> <드롭캡인셋mpt> <정렬모드>
//                   <최소간격> <비율M> <최대조정량mpt> <최대간격mpt> <최대간격비율R>"
//       정렬모드: -1=없음, 0=라틴낱말간격, 1=CJK글자사이.
//       드롭캡줄수 0 + 드롭캡인셋 0 = 드롭캡 OFF(단일 버킷).
//   입력 1행~: "<진행mpt>\t<클러스터텍스트>"  (셰이프된 클러스터 하나당 한 행, 순서대로)
//   출력 각 줄:  "<시작클러스터> <끝클러스터배타> <줄나쁨도B>"
//   출력 마지막: "TOTAL <총비용B>"
//   오류 센티넬: "OUT_OF_BOUNDS" | "NO_PLAN"

let R = 100000000   // 1e8 비율 스케일 (ratio scale)
let B = 1000000     // 1e6 나쁨도/벌점 스케일 (badness/penalty scale)
let CAP = 25000     // 정렬 벌점 상한 (justification penalty cap)

// ── 공용 정수 보조 (shared integer helpers) ──
function 반올림나눗셈(분자: int, 분모: int) -> int {   // round-half-up, 음이 아닌 값만
  let 몫 = 분자 / 분모
  let 나머지 = 분자 % 분모
  if 나머지 >= (분모 + 1) / 2 { 몫 + 1 } else { 몫 }
}
function 절댓값(값: int) -> int { if 값 < 0 { 0 - 값 } else { 값 } }
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/any over a cluster's scalars; 빈 문자열 -> all=true, any=false) ──
function 모두한글분할(텍스트: string) -> bool {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !한글분할문자인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 모두줄머리금지(텍스트: string) -> bool {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !줄머리금지인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 일부줄머리금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄머리금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
function 일부줄끝금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄끝금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}

// ── 단어 전체 판정 (whole-string predicates; single-scalar equality) ──
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 }

// ── 이웃 클러스터 가드 (Option<string> neighbor guards) ──
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 {
  모두한글분할(현재) && 다음은라틴공백아님(다음) && 다음은줄머리금지없음(다음) && !일부줄끝금지(현재)
}

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

// ── 나쁨도: 고정소수 줄 나쁨도 (fixed-point line badness; justification=None 경로) ──
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 = 기본B + 500 * B }
  }
  if 여유 < 0 { 기본B = 기본B + 20000 * B + 반올림나눗셈(20000 * B * 비례R, R) }
  if 분할종류 == "latin_hyphen" { 기본B = 기본B + 65 * B }
  if 분할종류 == "hard_fallback" { 기본B = 기본B + 50000 * B }
  if 글자수 <= 2 { 기본B = 기본B + 275 * B }
  기본B = 기본B + 10 * B
  기본B
}

// ── 정렬벌점: CJK 글자사이 정렬 보조 (CJK justification helpers) ──
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 {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 정렬부호코드인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
function CJK간격후보인가(왼쪽: string, 오른쪽: string) -> bool { 단일CJK인가(왼쪽) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽) }
function 한글공백간격후보인가(왼쪽: string, 공백: string, 오른쪽: string) -> bool {
  단일CJK인가(왼쪽) && 낱말공백인가(공백) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽)
}
function CJK간격수(텍스트들: Array<string>, 시작: int, 끝: int) -> int {
  let mut 간격 = 0
  let mut i = 시작
  while i + 1 < 끝 { if CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 = 간격 + 1 }; i = i + 1 }
  i = 시작
  while i + 2 < 끝 {
    if 한글공백간격후보인가(텍스트들[i], 텍스트들[i + 1], 텍스트들[i + 2]) {
      if !CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 = 간격 + 1 }
      if !CJK간격후보인가(텍스트들[i + 1], 텍스트들[i + 2]) { 간격 = 간격 + 1 }
    }
    i = i + 1
  }
  간격
}

// ── 정렬벌점: 라틴 낱말간격 + CJK 글자사이 통합 (full justification penalty, Latin + CJK) ──
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 mut 원래너비 = 0
  let mut a = 0
  while a < 유효 { 원래너비 = 원래너비 + 진행[a]; a = a + 1 }
  if 원래너비 * 1000 < 목표너비 * 비율M { return CAP * B }
  let 조정량 = 목표너비 - 원래너비
  if 조정량 <= 1 { return 0 }
  if 조정량 > 최대조정량 { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }
  if 모드 == 0 {
    let mut 간격 = 0
    let mut j = 0
    while j < 유효 { if U0020인가(텍스트들[j]) { 간격 = 간격 + 1 }; j = j + 1 }
    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 mut 대표합 = 0
    let mut 대표수 = 0
    let mut 불량 = false
    let mut k = 0
    while k < 유효 {
      if 단일CJK인가(텍스트들[k]) {
        if 진행[k] <= 1 { 불량 = true }
        대표합 = 대표합 + 진행[k]
        대표수 = 대표수 + 1
      }
      k = k + 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
}

// ── 한 줄 정렬벌점: 한 후보 줄[start, endExcl) 에 대한 정렬 벌점을 슬라이스로 계산 ──
// 정렬모드 < 0 (없음) 이면 0. 마지막 줄이면 0(정렬벌점 자체가 마지막 줄에 0).
function 줄정렬벌점(진행: Array<int>, 클러스터들: Array<string>, 시작: int, 끝: int, 목표너비: int,
                    정렬모드: int, 최소간격: int, 비율M: int, 최대조정량: int, 최대간격: int,
                    최대간격비율R: int, 마지막인가: bool) -> int {
  if 정렬모드 < 0 { return 0 }
  if 마지막인가 { return 0 }
  let mut 줄진행: Array<int> = []
  let mut 줄텍스트: Array<string> = []
  let mut u = 시작
  while u < 끝 { 줄진행.push(진행[u]); 줄텍스트.push(클러스터들[u]); u = u + 1 }
  정렬벌점(줄진행, 줄텍스트, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 최대간격비율R, 정렬모드, false)
}

// ── 줄 목표너비: 드롭캡 줄수 안에서는 인셋만큼 줄어든 목표를 쓴다 (drop-cap line bucket inset) ──
// ATLAS Rust `line_target_width_mpt(line_index=버킷, 시작, ...)`와 바이트 단위로 동일하다:
//   기준 = if 시작 == 0 { 첫줄목표너비 } else { 목표너비 }   (첫줄목표는 본문의 첫 단위에서 시작하는 줄에만)
//   기준 - line_inset_mpt(버킷)                              (인셋은 버킷 < 드롭캡줄수 일 때만)
// 즉 첫줄목표 선택은 단위 시작(시작==0)으로, 인셋은 줄버킷(버킷)으로 키잉한다. 드롭캡 OFF(드롭캡줄수 0)면
// 인셋은 0 → 기준 그대로 → 단일 버킷에서 기존 동작과 바이트 단위 동일.
function 줄목표너비(버킷: int, 시작: int, 목표너비: int, 첫줄목표너비: int, 드롭캡줄수: int, 드롭캡인셋: int) -> int {
  let 기준 = if 시작 == 0 { 첫줄목표너비 } else { 목표너비 }
  if 버킷 < 드롭캡줄수 { 기준 - 드롭캡인셋 } else { 기준 }
}

// ── 처리: 스텝퍼 진입점 (parse header + units -> 최적분할 DP -> serialize plan) ──
function 처리(입력: string) -> string {
  let 줄들 = 입력.split("\n")
  let 헤더 = 줄들[0].split(" ")
  let 목표너비 = toInt(헤더[0]) ?? 0
  let 첫줄목표너비_원 = toInt(헤더[1]) ?? 0
  let 드롭캡줄수 = toInt(헤더[2]) ?? 0
  let 드롭캡인셋 = toInt(헤더[3]) ?? 0
  let 정렬모드 = toInt(헤더[4]) ?? -1
  let 최소간격 = toInt(헤더[5]) ?? 1
  let 비율M = toInt(헤더[6]) ?? 0
  let 최대조정량 = toInt(헤더[7]) ?? 0
  let 최대간격 = toInt(헤더[8]) ?? 0
  let 최대간격비율R = toInt(헤더[9]) ?? 0
  // 시드 캡(seam caps): 목표너비 ∈ [1, 23e9]. 위반 -> OUT_OF_BOUNDS (Rust pt_to_target_mpt와 동일).
  if 목표너비 <= 0 || 목표너비 > 23000000000 { return "OUT_OF_BOUNDS" }
  let 첫줄목표너비 = if 첫줄목표너비_원 <= 0 { 목표너비 } else { 첫줄목표너비_원 }

  let mut 클러스터들: Array<string> = []
  let mut 진행: Array<int> = []
  let mut li = 1
  while li < 줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    클러스터들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
    li = li + 1
  }
  let 개수 = 클러스터들.length

  // 접두합(prefix sums): 너비 / 글자수
  let mut 너비접두 = [0]
  let mut 글자접두 = [0]
  let mut i = 0
  while i < 개수 {
    너비접두.push(너비접두[i] + 진행[i])
    글자접두.push(글자접두[i] + 클러스터들[i].scalars().length)
    i = i + 1
  }

  let 분할점 = 분할점생성(클러스터들)
  let 분할점단위 = 분할점.단위들
  let 분할점종류 = 분할점.종류들
  let 분할점수 = 분할점단위.length

  // ── 최적분할 2-D DP: (분할점, 버킷) 상태 (ATLAS Rust build_optimized_plan과 바이트 단위 동일) ──
  // 드롭캡이 켜지면 한 줄의 인셋(따라서 목표너비, 따라서 비용)은 지금까지 방출한 줄 수(=버킷)에 따라 달라지므로,
  // 같은 분할점에 줄 수가 다른 두 경로가 도달하면 그 둘은 교환 불가능하다 → 버킷을 DP의 2번째 차원으로 둔다.
  //   버킷 = min(지금까지 방출한 줄 수, K) (K = min(드롭캡줄수, 3)).  버킷수 = K + 1.  OFF면 버킷수 = 1 (단일 차원,
  //   기존 동작과 바이트 단위 동일).  다음버킷 = min(이전버킷 + 1, 마지막버킷) (포화).
  // 2-D 상태는 평탄화(flatten)한다: 상태인덱스(ei, b) = ei * 버킷수 + b.  병렬 1-D 배열은 ei 오름차순, 그 안에서
  // 버킷 오름차순으로 push 된다.  각 상태는 (있음, 비용, 이전ei, 이전버킷, 줄비용)을 가진다.
  let 버킷수 = if 드롭캡줄수 <= 0 || 드롭캡인셋 <= 0 {
    1
  } else {
    (if 드롭캡줄수 < 3 { 드롭캡줄수 } else { 3 }) + 1
  }
  let 마지막버킷 = 버킷수 - 1

  // 상태[0][b]: 버킷 0만 존재(비용 0), 나머지 버킷은 부재.  (Rust states[0][0] = seed, 나머지 None.)
  let mut 상태있음: Array<bool> = []
  let mut 상태비용: Array<int> = []
  let mut 상태이전ei: Array<int> = []
  let mut 상태이전버킷: Array<int> = []
  let mut 상태줄나쁨: Array<int> = []
  let mut b0 = 0
  while b0 < 버킷수 {
    상태있음.push(b0 == 0)
    상태비용.push(0)
    상태이전ei.push(0)
    상태이전버킷.push(0)
    상태줄나쁨.push(0)
    b0 = b0 + 1
  }

  let mut ei = 1
  while ei < 분할점수 {
    let 끝단위 = 분할점단위[ei]
    let 끝종류 = 분할점종류[ei]
    let 이전시작 = if ei > 80 { ei - 80 } else { 0 }
    let 마지막인가 = 끝단위 == 개수
    // 이 분할점에 도달하는 최적 상태를 다음버킷별로 모은다(최선[다음버킷]).
    let mut 최선있음: Array<bool> = []
    let mut 최선비용: Array<int> = []
    let mut 최선이전ei: Array<int> = []
    let mut 최선이전버킷: Array<int> = []
    let mut 최선줄나쁨: Array<int> = []
    let mut nb = 0
    while nb < 버킷수 { 최선있음.push(false); 최선비용.push(0); 최선이전ei.push(0); 최선이전버킷.push(0); 최선줄나쁨.push(0); nb = nb + 1 }

    let mut pi = 이전시작
    while pi < ei {
      let 시작 = 분할점단위[pi]
      if 시작 < 끝단위 {
        let 너비 = 너비접두[끝단위] - 너비접두[시작]
        let mut 이전버킷 = 0
        while 이전버킷 < 버킷수 {
          if 상태있음[pi * 버킷수 + 이전버킷] {
            // 새 줄은 (인셋 목적상) 이전버킷-번째 줄이다 (버킷 == 인셋의 유효 줄 인덱스).  첫줄목표는 단위 시작(시작==0)으로 키잉.
            let 이줄목표 = 줄목표너비(이전버킷, 시작, 목표너비, 첫줄목표너비, 드롭캡줄수, 드롭캡인셋)
            if !(너비 > 이줄목표 + 1 && 끝단위 > 시작 + 1) {
              let mut 공백수 = 0
              let mut u = 시작
              while u < 끝단위 { if 분할가능라틴공백인가(클러스터들[u]) { 공백수 = 공백수 + 1 }; u = u + 1 }
              let 줄나쁨 = 나쁨도(너비, 이줄목표, 글자접두[끝단위] - 글자접두[시작], 공백수, 끝종류, 마지막인가)
              let 정렬 = 줄정렬벌점(진행, 클러스터들, 시작, 끝단위, 이줄목표, 정렬모드, 최소간격, 비율M,
                                    최대조정량, 최대간격, 최대간격비율R, 마지막인가)
              let 줄비용 = 줄나쁨 + 정렬
              let 후보비용 = 상태비용[pi * 버킷수 + 이전버킷] + 줄비용
              let 다음버킷 = if 이전버킷 + 1 < 마지막버킷 { 이전버킷 + 1 } else { 마지막버킷 }
              // strict `<` keep-first: 오름차순 pi·버킷 루프이므로 정확한 i64 동점은 첫(가장 낮은) 전임자가 이긴다.
              if !최선있음[다음버킷] || 후보비용 < 최선비용[다음버킷] {
                최선있음[다음버킷] = true
                최선비용[다음버킷] = 후보비용
                최선이전ei[다음버킷] = pi
                최선이전버킷[다음버킷] = 이전버킷
                최선줄나쁨[다음버킷] = 줄비용
              }
            }
          }
          이전버킷 = 이전버킷 + 1
        }
      }
      pi = pi + 1
    }

    let mut wb = 0
    while wb < 버킷수 {
      상태있음.push(최선있음[wb])
      상태비용.push(최선비용[wb])
      상태이전ei.push(최선이전ei[wb])
      상태이전버킷.push(최선이전버킷[wb])
      상태줄나쁨.push(최선줄나쁨[wb])
      wb = wb + 1
    }
    ei = ei + 1
  }

  let 마지막 = 분할점수 - 1
  // 종단 최소: 버킷 가로질러 i64 strict `<` keep-first, 가장 낮은 버킷 먼저.  OFF면 버킷 0만 존재.
  let mut 종단버킷 = -1
  let mut tb = 0
  while tb < 버킷수 {
    if 상태있음[마지막 * 버킷수 + tb] {
      if 종단버킷 < 0 || 상태비용[마지막 * 버킷수 + tb] < 상태비용[마지막 * 버킷수 + 종단버킷] {
        종단버킷 = tb
      }
    }
    tb = tb + 1
  }
  if 종단버킷 < 0 { return "NO_PLAN" }

  // 역추적(reversed 수집): (분할점, 버킷) 셀을 이전버킷을 따라 거슬러 걷는다.
  let mut 역시작: Array<int> = []
  let mut 역끝: Array<int> = []
  let mut 역줄: Array<int> = []
  let mut wi = 마지막
  let mut wbucket = 종단버킷
  while wi > 0 {
    let 셀 = wi * 버킷수 + wbucket
    역시작.push(분할점단위[상태이전ei[셀]])
    역끝.push(분할점단위[wi])
    역줄.push(상태줄나쁨[셀])
    let 다음wi = 상태이전ei[셀]
    wbucket = 상태이전버킷[셀]
    wi = 다음wi
  }
  let mut 출력 = ""
  let mut 총비용 = 0
  let mut k = 역시작.length - 1
  while k >= 0 {
    출력 = if 출력 == "" { "{역시작[k]} {역끝[k]} {역줄[k]}" } else { "{출력}\n{역시작[k]} {역끝[k]} {역줄[k]}" }
    총비용 = 총비용 + 역줄[k]
    k = k - 1
  }
  "{출력}\nTOTAL {총비용}"
}

print(처리(input()))

// ATLAS 최적분할 — 고정소수 줄바꿈 DP (optimal-fit integer DP).
// dp.tpz 의 한국어 식별자 번역. 동작은 바이트 단위로 동일하다(dp_fp.rs ≡ ATLAS Rust B5).
// 범위: 드롭캡 OFF(단일 버킷), 첫줄=목표, 정렬=없음. 금칙분류 + 나쁨도 + 정수 DP 를 인라인한다.
// I/O: stdin "<목표너비mpt>\n<진행mpt>\t<텍스트>\n..." -> "<시작> <끝배타> <줄나쁨도B>\n...TOTAL <B>".

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 {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !한글분할문자인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 모두줄머리금지(텍스트: string) -> bool {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !줄머리금지인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 일부줄머리금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄머리금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
function 일부줄끝금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄끝금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
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 { 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 = 기본B + 500 * B }
  }
  if 여유 < 0 { 기본B = 기본B + 20000 * B + 반올림나눗셈(20000 * B * 비례R, R) }
  if 분할종류 == "latin_hyphen" { 기본B = 기본B + 65 * B }
  if 분할종류 == "hard_fallback" { 기본B = 기본B + 50000 * B }
  if 글자수 <= 2 { 기본B = 기본B + 275 * B }
  기본B = 기본B + 10 * B
  기본B
}

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

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

print(처리(input()))

// ATLAS 나쁨도 — 고정소수 줄 나쁨도 (fixed-point line badness).
// badness.tpz 의 한국어 식별자 번역. 동작은 바이트 단위로 동일하다(badness_fp.rs ≡ ATLAS Rust).
// I/O: stdin 줄 "<너비>|<목표너비>|<글자수>|<공백수>|<분할종류>|<마지막인가(0/1)>" -> 줄당 나쁨도 B-단위.

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 { 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 = 기본B + 500 * B }
  }
  if 여유 < 0 {
    기본B = 기본B + 20000 * B + 반올림나눗셈(20000 * B * 비례R, R)
  }
  if 분할종류 == "latin_hyphen" { 기본B = 기본B + 65 * B }
  if 분할종류 == "hard_fallback" { 기본B = 기본B + 50000 * B }
  if 글자수 <= 2 { 기본B = 기본B + 275 * B }
  기본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 금칙분류 — 줄바꿈 기회 분류기 (break-opportunity classifier / kinsoku).
// linebreak-classify.tpz 의 한국어 식별자 번역. 동작은 바이트 단위로 동일하다.
// 순수·결정론: 클러스터(한 줄당 하나) -> 줄바꿈 기회("<단위끝> <분할종류>").
// /root/atlas/core/typesetting/src/vnext_paragraph.rs 의 build_break_opportunities 와 동일.
// 분할종류 토큰(latin_space/korean_cluster/...)은 ASCII 유지(seam I/O 계약).
//
// I/O: stdin 클러스터(한 줄당 하나) -> "<단위끝> <분할종류>" 한 줄당 한 기회.

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 {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !한글분할문자인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 모두줄머리금지(텍스트: string) -> bool {
  let mut 참 = true
  for 스칼라 in 텍스트.scalars() { if !줄머리금지인가(첫코드포인트(스칼라)) { 참 = false } }
  참
}
function 일부줄머리금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄머리금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
function 일부줄끝금지(텍스트: string) -> bool {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 줄끝금지인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}

// ── 단어 전체 판정 (single-scalar equality, `matches!` 대응) ──
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 }

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

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

// ATLAS 정렬벌점 — 고정소수 정렬 벌점 (Latin + CJK justification penalty).
// just.tpz 의 한국어 식별자 번역. 동작은 바이트 단위로 동일하다(just_fp.rs ≡ ATLAS Rust).
// I/O: stdin 헤더 "<목표너비> <최소간격> <비율M> <최대조정량> <최대간격> <최대간격비율R> <모드> <마지막인가>"
//      이어서 "<진행>\t<텍스트>" 줄들 -> 단일 정렬 벌점 B-단위.

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 {
  let mut 발견 = false
  for 스칼라 in 텍스트.scalars() { if 정렬부호코드인가(첫코드포인트(스칼라)) { 발견 = true } }
  발견
}
function CJK간격후보인가(왼쪽: string, 오른쪽: string) -> bool { 단일CJK인가(왼쪽) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽) }
function 한글공백간격후보인가(왼쪽: string, 공백: string, 오른쪽: string) -> bool {
  단일CJK인가(왼쪽) && 낱말공백인가(공백) && 단일CJK인가(오른쪽) && !정렬부호단위인가(왼쪽) && !정렬부호단위인가(오른쪽)
}
function CJK간격수(텍스트들: Array<string>, 시작: int, 끝: int) -> int {
  let mut 간격 = 0
  let mut i = 시작
  while i + 1 < 끝 { if CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 = 간격 + 1 }; i = i + 1 }
  i = 시작
  while i + 2 < 끝 {
    if 한글공백간격후보인가(텍스트들[i], 텍스트들[i + 1], 텍스트들[i + 2]) {
      if !CJK간격후보인가(텍스트들[i], 텍스트들[i + 1]) { 간격 = 간격 + 1 }
      if !CJK간격후보인가(텍스트들[i + 1], 텍스트들[i + 2]) { 간격 = 간격 + 1 }
    }
    i = i + 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 mut 원래너비 = 0
  let mut a = 0
  while a < 유효 { 원래너비 = 원래너비 + 진행[a]; a = a + 1 }
  if 원래너비 * 1000 < 목표너비 * 비율M { return CAP * B }
  let 조정량 = 목표너비 - 원래너비
  if 조정량 <= 1 { return 0 }
  if 조정량 > 최대조정량 { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }
  if 모드 == 0 {
    let mut 간격 = 0
    let mut j = 0
    while j < 유효 { if U0020인가(텍스트들[j]) { 간격 = 간격 + 1 }; j = j + 1 }
    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 mut 대표합 = 0
    let mut 대표수 = 0
    let mut 불량 = false
    let mut k = 0
    while k < 유효 {
      if 단일CJK인가(텍스트들[k]) {
        if 진행[k] <= 1 { 불량 = true }
        대표합 = 대표합 + 진행[k]
        대표수 = 대표수 + 1
      }
      k = k + 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> = []
  let mut li = 1
  while li < 줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    텍스트들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
    li = li + 1
  }
  "{정렬벌점(진행, 텍스트들, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 최대간격비율R, 모드, 마지막인가)}"
}

print(처리(input()))

// ATLAS 라틴정렬벌점 — 고정소수 라틴 낱말간격 정렬 벌점 (LatinWordSpace justification penalty).
// just_latin.tpz 의 한국어 식별자 번역. 동작은 바이트 단위로 동일하다(just_latin_fp.rs ≡ ATLAS Rust).
// I/O: stdin 헤더 "<목표너비> <최소간격> <비율M> <최대조정량> <최대간격> <마지막인가>"
//      이어서 "<진행>\t<텍스트>" 줄들 -> 단일 정렬 벌점 B-단위.

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 mut 원래너비 = 0
  let mut i = 0
  while i < 유효 { 원래너비 = 원래너비 + 진행[i]; i = i + 1 }
  if 원래너비 * 1000 < 목표너비 * 최소라틴비율M { return CAP * B }
  let 조정량 = 목표너비 - 원래너비
  if 조정량 <= 1 { return 0 }
  if 조정량 > 최대조정량 { return CAP * B + 반올림나눗셈((조정량 - 최대조정량) * B, 1000) }
  let mut 간격수 = 0
  let mut j = 0
  while j < 유효 { if U0020인가(텍스트들[j]) { 간격수 = 간격수 + 1 }; j = j + 1 }
  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> = []
  let mut li = 1
  while li < 줄들.length {
    let 부분들 = 줄들[li].split("\t")
    진행.push(toInt(부분들[0]) ?? 0)
    텍스트들.push(if 부분들.length >= 2 { 부분들[1] } else { "" })
    li = li + 1
  }
  "{라틴정렬벌점(진행, 텍스트들, 목표너비, 최소간격, 비율M, 최대조정량, 최대간격, 마지막인가)}"
}

print(처리(input()))