// 아틀라스 최적분할. 전체 비용이 가장 낮은 줄 분할을 고르는 고정소수 정수 DP 명세다(optimal-fit integer DP).
// 통합 줄바꿈기 `줄바꿈.tpz`의 4단계(정수 동적계획법)를 따로
// 떼어 적었다.
// 범위는 드롭캡 OFF(단일 버킷), 첫줄=목표, 정렬=없음이다. 1·2·4단계(금칙분류·나쁨도·정수 DP)를 한 파일에 인라인한다.
// 드롭캡·첫줄목표·정렬을 더한 2차원 (분할점, 버킷) 전체 DP는 통합본 `줄바꿈.tpz`에 있다.
// 입출력. 표준입력으로 "<목표너비mpt>\n<진행mpt>\t<텍스트>\n..."를 받아 "<시작> <끝배타> <줄나쁨도B>\n...TOTAL <B>"를 낸다.

import std.io

let R = 100000000
let B = 1000000

// ── 금칙분류 ──
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
  || 코드 == 8217 || 코드 == 8230 || 코드 == 65289 || 코드 == 12305 || 코드 == 65341 || 코드 == 65373 || 코드 == 65292 || 코드 == 65294 || 코드 == 65307 || 코드 == 65306 || 코드 == 65281 || 코드 == 65311 || 코드 == 187 || 코드 == 8250
}
function 줄끝금지인가(코드: int) -> bool {
  코드 == 40 || 코드 == 91 || 코드 == 123 || 코드 == 12300 || 코드 == 12302 || 코드 == 12298 || 코드 == 12296
  || 코드 == 65288 || 코드 == 12304 || 코드 == 65339 || 코드 == 65371 || 코드 == 171 || 코드 == 8249
}
function 모두한글분할(텍스트: string) -> bool {
  텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 한글분할문자인가(첫코드포인트(스칼라)))
}
function 모두줄머리금지(텍스트: string) -> bool {
  텍스트.scalars().reduce(true, (참: bool, 스칼라: string) => 참 && 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄머리금지(텍스트: string) -> bool {
  텍스트.scalars().reduce(false, (발견: bool, 스칼라: string) => 발견 || 줄머리금지인가(첫코드포인트(스칼라)))
}
function 일부줄끝금지(텍스트: string) -> bool {
  텍스트.scalars().reduce(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 공백코드인가(코드: int) -> bool {
  (코드 >= 9 && 코드 <= 13) || 코드 == 32 || 코드 == 133 || 코드 == 160 || 코드 == 5760
  || (코드 >= 8192 && 코드 <= 8202) || 코드 == 8232 || 코드 == 8233 || 코드 == 8239 || 코드 == 8287 || 코드 == 12288
}
function 여는직선따옴표인가(글자들: Array<string>, 위치: int) -> bool {
  let 코드 = 첫코드포인트(글자들[위치])
  if (코드 != 34 && 코드 != 39) { return false }
  if (위치 == 0) { return true }
  let 앞 = 첫코드포인트(글자들[위치 - 1])
  공백코드인가(앞) || 줄끝금지인가(앞)
}
function 라틴낱말코드인가(코드: int) -> bool {
  (코드 >= 65 && 코드 <= 90) || (코드 >= 97 && 코드 <= 122)
  || (코드 >= 192 && 코드 <= 591) || (코드 >= 7680 && 코드 <= 7935)
}
function 문맥경계허용인가(글자들: Array<string>, 경계: int) -> bool {
  let mut 왼쪽 = 경계 - 1
  while (왼쪽 >= 0) {
    if (!공백코드인가(첫코드포인트(글자들[왼쪽]))) { break }
    왼쪽 -= 1
  }
  if (왼쪽 > 0 && 왼쪽 + 1 < 글자들.length) {
    let 코드 = 첫코드포인트(글자들[왼쪽])
    if ((코드 == 8217 || 코드 == 39) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 - 1])) && 라틴낱말코드인가(첫코드포인트(글자들[왼쪽 + 1]))) { return false }
  }
  if (왼쪽 >= 0) {
    if (줄끝금지인가(첫코드포인트(글자들[왼쪽])) || 여는직선따옴표인가(글자들, 왼쪽)) { return false }
  }
  let mut 오른쪽 = 경계
  while (오른쪽 < 글자들.length) {
    if (!공백코드인가(첫코드포인트(글자들[오른쪽]))) { break }
    오른쪽 += 1
  }
  if (오른쪽 < 글자들.length) {
    let 코드 = 첫코드포인트(글자들[오른쪽])
    if (줄머리금지인가(코드)) { return false }
    if ((코드 == 34 || 코드 == 39) && !여는직선따옴표인가(글자들, 오른쪽)) { return false }
    if (코드 == 8212) {
      if (오른쪽 > 0 && 줄머리금지인가(첫코드포인트(글자들[오른쪽 - 1]))) { return false }
      if (오른쪽 + 1 < 글자들.length && 줄머리금지인가(첫코드포인트(글자들[오른쪽 + 1]))) { return false }
    }
  }
  true
}

function 분할점생성(클러스터들: Array<string>) -> { 단위들: Array<int>, 종류들: Array<string> } {
  let 개수 = 클러스터들.length
  let mut 전체텍스트 = ""
  for 단위 in (클러스터들) { 전체텍스트 = 전체텍스트 + 단위 }
  let 글자들 = 전체텍스트.scalars()
  let mut 글자끝 = 0
  let mut 단위들 = [0]
  let mut 종류들 = ["forced_end"]
  for i in (0..<개수) {
    let 단위 = 클러스터들[i]
    let 단위끝 = i + 1
    글자끝 += 단위.scalars().length
    let 이전: Option<string> = 클러스터들.get(i - 1)
    let 다음 = 클러스터들.get(단위끝)
    let 결과: { 종류: string, 내보냄: bool } = match (true) {
      case _ if (단위끝 == 개수) => { 종류: "forced_end", 내보냄: true }
      case _ if (!문맥경계허용인가(글자들, 글자끝)) => { 종류: "", 내보냄: false }
      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 목표 = 줄들[0].toInt() ?? 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(부분들[0].toInt() ?? 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 {총비용}"
}

io.writeLine(처리(io.readStdin()))
