Segment a message with width-constrained suffixes

Given a message string s and an integer width W, split s into consecutive segments and append a suffix "i/n" to each segment indicating its 1-indexed position i out of the total n segments. Part A (suffix excluded from width): Split s into chunks of up to W characters (not counting the suffix), then append the suffix to each line; return the list of lines. Part B (suffix included in width): Now len(chunk) + len(suffix(i,n)) must be ≤ W for every line, but n is unknown in advance because the suffix length depends on n. Produce valid lines that cover the entire message in order (breaking anywhere is allowed; no reordering). If impossible (e.g., W < len("1/1")), return an error. Implement an efficient algorithm to determine n and the segmentation and analyze its complexity.