Little Shop Of Flowers

PROBLEM

I din blomsterforretning ønsker du at arrangere  udstillingsvinduet på den mest indbydende må­de. Du har F bundter blomster, alle af indbyr­des forskellig art, og mindst lige så mange vaser pla­ceret på række. Vaserne er limet fast til hyl­den og er nummereret fra 1 til V, hvor V er antal­let af vaser, således at vasen længst til venstre har num­mer 1 og den længst til højre har num­mer V. Blomsterbundterne kan flyttes omkring og er entydigt nummererede fra 1 til F. Disse id-numre har en betydning for bundternes place­ring, idet de fortæller i hvilken rækkefølge bundt­erne kan placeres i vaserne: bundt nummer i skal placeres i en vase som er længere til venstre end den vase, der indeholder bundt nummer j, når i<j.

Tag som eksempel følgende, hvor du har et bundt azalea (id-nummer=1), et bundt begonia (id-nummer=2) og et bundt nelliker (id-num­mer=3). Alle bundterne skal placeres i vaser, og deres id-numre skal komme i rækkefølge. Azaleaerne skal således være i en vase til venstre for begonierne, som igen skal være i en vase til venstre for nellikerne.

Alle bundter skal placeres i en vase, og hvis der er flere vaser end bundter, efterlades de over­skydende tomme. Der kan højst placeres ét bundt i hver vase.

Hver vase har sit eget særpræg – ligesom jo også blomsterne har det. Derfor vil placeringen af et bundt resultere i en bestemt æstetisk værdi, givet ved et heltal. Den æstetiske værdi er angivet i en tabel som nedenstående. En tom vase vil have den æstetiske værdi 0.

		V A S E R
		1	2	3	4	5
Bundter	1 (azalea)	7	23	-5	-24	16
	2 (begonia)	5	21	-4	10	23
	3 (nellike)	-21	5	-4	-20	20

I følge tabellen vil for eksempel azaleaer se flotte ud i vase 2, mens de vil være gyselige i vase 4.

For at opnå det mest indbydende vindue, skal du maksimere den æstetiske værdi af arrange­ment­et, samtidig med at bundterne kommer i den rig­ti­ge rækkefølge. Hvis mere end ét arrangement giver den maksimale værdi, skal du kun angive ét af dem.

ANTAGELSER

·      1 £ F £ 100, hvor F er antallet af bundter. Bundterne er nummereret fra 1 til F.

·      F £ V £ 100, hvor V er antallet af vaser.

·     -50 £ A_ij £ 100, hvor A_ij er den æstetiske værdi af bundt nummer i i vase j.

INPUT

Input læses fra tekstfilen FLOWER.INP.

·      Den første linje indeholder to tal: F og V.

·     I hver af de følgende F linjer står V heltal, således at A_ij er det j’te tal på den (i+1)’te linje i inputfilen.

OUTPUT

Output skal skrives til tekstfilen FLOWER.OUT, som skal bestå af to linjer:

·      Den første linje skal indeholde summen af æstetiske værdier for dit arrangement.

·     Den anden linje skal præsentere arrangementet som en række af F heltal, hvor det k’te tal er nummeret på vasen, hvor bundt k er placeret.

EKSEMPEL

FLOWER.INP:

FLOWER.OUT: