PRINT.c

#include<stdio.h>

#define MAX 1000

int plLength[MAX],lMpl,plDp[MAX],plMin[MAX],lTotal;

char pstrWords[MAX][64];

int strLen(char *str)
{
	char *tmp=str;
	while(*tmp!='\0')
		tmp++;
	return tmp-str;
}

int Find(int lNow)
{
	int min,i;
	if(plMin[lNow]!=-1)
		return plMin[lNow];
	if(plLength[lTotal]-plLength[lNow-1]+lTotal-lNow<=lMpl)
	{
		plMin[lNow]=0;
		plDp[lNow]=lTotal;
		return 0;
	}
	min=(lMpl-plLength[lNow]+plLength[lNow-1])*(lMpl-plLength[lNow]+plLength[lNow-1])*(lMpl-plLength[lNow]+plLength[lNow-1])+Find(lNow+1);
	plDp[lNow]=lNow;
	for(i=lNow+1;plLength[i]-plLength[lNow-1]+i-lNow<=lMpl;i++)
	{
		if((lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))*(lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))*(lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))+Find(i+1)<min)
		{
			min=(lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))*(lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))*(lMpl-(plLength[i]-plLength[lNow-1]+i-lNow))+Find(i+1);
			plDp[lNow]=i;
		}
	}
	plMin[lNow]=min;
	return min;
}

int main()
{
	int i,j,k;
	scanf("%d %d",&lTotal,&lMpl);
	for(i=1;i<=lTotal;i++)
	{
		scanf("%s",&pstrWords[i][0]);
		plLength[i]=plLength[i-1]+strLen(&pstrWords[i][0]);
		plMin[i]=-1;
	}
	Find(1);
//	printf("%d",plMin[1]);
	for(i=1,j=plDp[i]+1;i<=lTotal;i=j,j=plDp[i]+1)
	{
		for(k=i;k<j;k++)
		{
			printf("%s ",&pstrWords[k][0]);
		}
		printf("\n");
	}
}
/*
999 32
money
nurse
policewoman
thief
uniform
abacus
abbreviation
accessory
accident
accordion
achievement
action
activity
actor
address
adult
advantage
adverb
advertisement
advertising
advice
Africa
afternoon
age
agent
aid
airplane
airport
album
alien
America
amount
amusement
ancestor
animal
answer
ant
apartment
apple
appointment
April
aquarium
area
arm
art
article
artist
assistant
association
astronaut
athlete
attendant
attention
attitude
attraction
August
aunt
Australia
author
authority
autograph
autumn
avenue
award
baby
backboard
backpack
bag
bakery
balance
ball
banana
band
bank
barbecue
bargain
baseball
basket
basketball
bat
bathing
bathroom
battery
beach
beard
beauty
bed
bedroom
beef
beginning
behavior
bell
belt
bench
beverage
bicycle
bike
bingo
binoculars
biology
bird
birth
birthday
biscuit
bit
blank
blender
block
board
boat
body
book
bookcase
bookstore
border
bowl
box
boy
bracket
bread
breakfast
bridge
broccoli
brother
building
bulb
bus
bush
business
butter
cabbage
cafe
cage
cake
calculator
calendar
camel
camera
campaign
Canada
cancer
candy
capital
captain
car
card
carrot
case
cat
cathedral
center
century
chair
challenge
champion
championship
chance
character
charity
chatline
cheese
cheetah
chef
chemistry
chess
chicken
child
children
chimpanzee
Chinese
chip
chocolate
chore
church
cigarette
cinema
circle
city
class
classmate
classroom
clean-up
clerk
clock
clothes
clothing
clown
club
coffee
coin
cola
collection
collector
colon
color
comedy
comic
comma
comment
commitment
company
competition
compliment
computer
concert
conclusion
conjunction
consequence
contest
contraction
conversation
cookie
corner
costume
country
countryside
course
court
cousin
cow
cream
creature
cruise
culture
cup
cupboard
curry
custom
dad
danger
Dangshen
dark
date
daughter
day
death
December
decision
deli
dentist
department
description
design
desk
dessert
development
dictionary
diet
difference
diner
dining
dinner
direction
director
disadvantage
disagreement
dish
distance
district
doctor
documentary
dog
dollar
dolphin
donation
door
dormitory
drawer
dreamer
dresser
drugstore
drum
duck
dumpling
duty
ear
earring
earth
earthquake
egg
elbow
elephant
elevator
e-mail
emoticon
emotion
emperor
end
ending
energy
engineer
English
entertainment
envelope
environment
equator
equipment
eraser
Erhu
escalator
essay
etiquette
Europe
evening
exam
example
exclamation
exhibition
experience
expression
eye
fact
factory
family
fan
farm
farmer
fashion
father
fax
feature
February
fence
festival
fever
fiction
fight
film
finding
finger
firm
first-aid
fish
fisherman
fishing
flashcard
flight
floor
flower
fly
food
foot
football
footstep
foreigner
fork
fox
France
freedom
French
Friday
friend
friendship
front
fruit
furniture
future
gallery
game
garage
garbage
garden
geography
gift
giraffe
girl
girlfriend
glasses
globe
golfer
government
grade
graduate
grammar
grandfather
grandmother
grandpa
grandparent
grandson
grass
Greenpeace
group
guidebook
guitar
gum
guy
gym
gymnast
habit
habitat
hair
haircut
hall
Halloween
hallway
hamburger
hamster
hand
hat
head
headache
health
heart
heel
helicopter
hen
herb
hero
history
hit
hoax
hobby
holiday
homeland
hometown
homework
homophone
honey
hoop
hospital
host
hotel
hour
house
housework
Huangqi
huge
Hugeman
human
hunger
husband
Hutung
ice
idea
illness
importance
infinitive
information
ingredient
insect
inspiration
instance
instruction
instrument
Internet
interviewer
invitation
island
January
Japan
jazz
jeans
Jew
job
joke
juice
July
June
jungle
junk
kangaroo
key
kilometer
king
kiss
kitchen
kite
knee
knife
koala
laboratory
lady
lagoon
lake
language
lap
laundry
lawyer
leader
leaf
learner
leg
legend
lemon
lesson
letter
lettuce
library
license
life
lifestyle
lighting
line
lion
listener
litter
lookout
lot
lunch
lyric
madam
magazine
magic
mail
mall
man
management
manatee
mangrove
manner
map
marathon
March
mark
market
Mars
match
material
math
May
meal
meaning
means
meat
medal
meeting
member
menu
mess
message
metal
meter
microwave
mile
milk
minute
Miss
mistake
mixture
model
mom
moment
Monday
monitor
monkey
monster
month
moon
morning
mother
mountain
mouse
mouth
movie
museum
music
musician
mutton
mystery
name
napkin
nature
neck
neighbor
neighborhood
net
news
newsletter
newspaper
night
noise
noodle
noon
north
nose
note
notebook
November
number
oak
ocean
October
octopus
office
onion
opera
opinion
opportunity
optometrist
orange
organization
owner
Pacific
pain
pair
pal
palace
pancake
panda
panic
pants
paper
parent
Paris
parrot
part
partner
party
passenger
pear
pen
pencil
penguin
people
performer
permission
person
pet
phone
photo
photograph
photographer
photography
phrase
physics
pianist
piano
picnic
pie
piece
pig
pilot
pimple
place
plane
planet
plant
player
playground
pleasure
plural
poem
police
policeman
pollution
pool
pop
popcorn
popper
popularity
population
porridge
post
postcard
poster
potato
pound
prediction
preposition
president
pressure
price
prize
problem
product
program
programmer
programming
progress
project
pronoun
pronunciation
province
psychologist
public
punctuation
purple
purpose
purse
quality
quarter
question
queue
rabbit
racket
radio
raincoat
rank
rat
rating
reader
reason
recipe
record
refrigerator
relative
relish
reporter
requirement
research
resolution
restaurant
restroom
result
review
rice
riddle
risk
river
robot
rock
rocket
roof
room
root
route
rubbish
rule
ruler
runner
safari
safety
salad
sale
salt
sandwich
Saturday
sauce
saying
scarf
scene
school
schoolbag
schoolwork
science
scientist
scoop
screen
sea
seal
season
seat
secret
semester
sentence
September
service
sex
shampoo
shape
shark
shelf
shell
shirt
shoe
shop
shorts
show
sight
sightseeing
sign
silence
singer
single
singular
sir
sister
sitcom
situation
size
skater
skill
skin
skirt
sky
sleep
slice
slipper
slogan
smell
snack
snake
soap
soccer
society
sock
sofa
soldier
solution
son
song
soup
south
southeast
souvenir
space
spaghetti
speech
spider
spokesperson
spoon
sport
sportspeople
spot
spotlight
spring
square
staff
stage
stamp
stardust
statement
station
step
stomach
stomachache
stone
story
strategy
strawberry
street
string
structure
student
stuff
style
subject
subway
success
suggestion
suitcase
summer
Sunday
sunglasses
supermarket
survey
swamp
sweater
symbol
symphony
table
tag
talent
tape
task
taxi
tea
teacher
team
teaspoon
teen
teenager
teeth
telephone
temperature
tennis
term
terrorist
test
theater
theme
thing
thought
thousand
thriller
throat
Thursday
ticket
tie
tiger
tile
time
tofu
tomato
tomorrow
tonight
tooth
toothache
toothbrush
top
topic
tourist
towel
tower
town
toy
traffic
tragedy
train
training
translator
transportation
trash
tree
trip
trumpet
truth
tuesday
turkey
turtle
tutor
umbrella
uncle
unit
university
vacation
vegetable
verb
veterinarian
view
village
villager
violin
violinist
visitor
vocabulary
voice
volleyball
volunteer
waiter
waitress
wall
wallet
watermelon
wave
way
weather
website
Wednesday
week
weekday
weekend
wheel
window
wine
winner
winter
Wiseman
wish
woman
wood
word
world
writer
yang
yard
year
yesterday
yin
yogurt
zigzag
zoo
Japanese
west
today
hundred
aim
camp
care
dream
drink
drive
exchange
form
guide
heat
influence
interest
interview
kid
land
list
matter
order
park
plan
point
report
ride
ring
shake
shop
shower
skate
star
store
suit
talk
tour
trouble
type
walk
watch
water
worker
fucke
shiter
fucker
rocketer
*/