Final Combat

You’re playing an RPG, which is arguably the best Chinese RPG in 2007. You got to the final combat. You want to win as soon as possible. Do you know what I am talking about?

For competitors who're not familiar with the game: we're giving a brief introduction to the combat system and the characters involved in that last combat very soon.

For competitors who're too familiar with the game: we're simplifying and/or changing the rules and facts for this problem. We apologize if you feel unhappy about that.


Fig. The final combat
The screenshot above gives you some idea about the combat system and the characters, which can be summarized as follows:

You have 4 heroes: Yun Tianhe (YTH), Han Lingsha (HLS), Liu Mengli (LML) and Murong Ziying (MRZY). Before the combat begins, you need to choose exactly three heroes and rearrange them in some order. Let's call the 1st, 2nd and 3rd hero H1, H2 and H3, respectively. In this screenshot above, H1 is YTH, H2 is HLS and H3 is LML. (Sorry for the Ziying fans!)

There are two bosses: Xuan Xiao (XX) and Su Yao (SY), both in the back of the screenshot.

The goal of this combat is to defeat SY. In this problem, you can assume that XX is immortal, although it's possible to defeat him in the real game.

The key to this problem is to understand the "semi" round-based combat system. See the "progress bar" on the top of the screen? Each hero has a very small progress ball (in light-blue) on the bar, with an icon above the ball. Similarly, each boss also has a ball (in red), but the icon is below the ball. When the combat begins, all the progress balls start moving from the left corner of the bar. When a ball reaches the right corner, the corresponding character is able to act. If more than one character can act, they make actions one by one, according to this precedence order: YTH, HLS, LML, MRZY, XX, SY. When a character is acting, all progress balls stopped moving. After a character finished an action, his/her progress ball is reset to the left corner of the progress bar. When nobody is acting, all progress balls go right simultaneously (but possibly with different speeds, see below).

In this problem, each character has 4 main properties: Jing, Qi, Shen, Su.

Jing means "health". When a character's Jing reaches zero or negative, he/she is defeated. A character's maximum Jing is denoted by parameter maxjing.

Qi means "vitality". It is used by special-skill attacks. When Qi is not enough, certain special-skill attacks cannot be performed. A character's maximum Qi is always 100.

Shen means "spirit". It is used by Xian Shu (something similar to, but more amazing than "magic"). When Shen is not enough, certain Xian Shu cannot be performed. A character's maximum Shen is denoted by parameter maxshen.

Su means "speed". It affects how quick a character's progress ball moves. Su is always a positive integer less than 5. If a character's Su is x, it takes 5-x units time for his/her progress ball to move from left corner to the right corner of the progress bar. A character's Su (which is never changed during the combat) is denoted by parameter su.

For simplicity, you may assume that both XX and SY use the same strategy:

In his/her (4n+1)-th action (n=0,1,2,...), make a weapon attack upon H1.

In his/her (4n+2)-th action (n=0,1,2,...), make a weapon attack upon H2.

In his/her (4n+3)-th action (n=0,1,2,...), make a weapon attack upon H3.

In his/her (4n+4)-th action (n=0,1,2,...), make a special-skill attack upon all the heroes.

Now we introduce four more parameters for each hero. The first two, d1x and d2x, are the damages that the hero takes on XX's weapon attack and special-skill attack, respectively. For SY's attacks, we define d1s and d2s similarly.

You’re very tired, so you don't want to waste your time designing complex tactics. When a hero is about to act, you only consider the following actions:

Make a physical weapon attack upon either XX or SY (cannot attack both). Be warned though, SY is surrounded by swords (see the screenshot), so making weapon attacks upon her would hurt the attacker himself/herself. The amount of "reflection damage" that the attacker takes is the same as the "physical damage" that SY takes. Attacking XX (yes, you can do that, if you like) does not suffer from physical reflection.

Use Xian Shu to recover Jing. To make your brain easier, you decided not to recover other heroes' Jing. In this problem, the only Xian Shu that you can use is called "Yu Run", which recovers yurun_jing points of Jing (if the resulting Jing exceeds his/her maximum Jing, it is reduced to the maximum) and uses yurun_shen points of Shen.

Use items to recover Shen. To make your brain easier, you decided not to recover other heroes' Shen. In this problem, the only item that you can use is called "Shu Er Guo", which recovers shuerguo_shen points of Shen (if the resulting Shen exceeds his/her maximum Shen, it is reduced to the maximum). You have an infinite number of Shu Er Guo.

Make a special-skill attack if his/her Qi is enough. Each hero has exactly one special-skill attack, attacking both XX and SY. Note that some special-skill attacks are physical. Using a physical special-skill attack makes you take the same damage as SY, just like weapon attacks.

Now it's time to introduce four more parameters for each hero: wad, ssd, ssq and ssp. The number of Jing points that SY takes by the hero's weapon attacks and special-skill attacks are denoted by wad and ssd, respectively. The special-skill attack is physical if and only if ssp=1 (otherwise, ssp=0). It needs ssq points of Qi.

As you may have noticed, Qi cannot be recovered by Xian Shu or items. There are only two ways to increase Qi: make a weapon attack, or get hit by a weapon attack. Being hurt by physical reflection does not earn you extra Qi.

So here come the last two parameters for each hero: q1 and q2, that means making a weapon attack increases q1 points of Qi (whether or not you're reflected), while getting hit by a weapon attack increases q2 points of Qi. If the resulting Qi exceeds his/her maximum Qi (which is always 100), it is reduced to the maximum. Again, performing a special-skill attack never increases your Qi. Getting hurt by the bosses' special-skill attacks never increases your Qi, either.

As a perfectionist, you don't want any hero to be defeated even temporarily (in the real game you can rebirth a hero with certain Xian Shu or items) - for example, it's not allowed to make YTH and SY defeated at the same time (it can happen, for example, after YTH has performed a powerful physical special-skill attack).

Finally comes the question: what is the earliest time (we only care about ball-moving time, not including time needed to make attacks) that you can win the combat, if you play optimally? To play optimally, you need to choose between the options listed above, for each act. It's not as easy as it sounds. Be careful!

There will be at most 100 test cases. Each case begins with 6 positive integers, SY_jing (SY's initial Jing), XX_su (XX's Su), SY_su (SY's Su), yurun_jing, yurun_shen and shuerguo_shen. The next four lines contain descriptions of YTH, HLS, LML and MRZY, in this order. Each line contains 16 non-negative integers: maxjing, maxshen, su, d1x, d2x, d1s, d2s, wad, ssd, ssq, ssp, q1, q2, jing, qi, shen. The last three parameters are the initial Jing, Qi and Shen values of this hero before the combat begins. The limits of most parameters are listed below:


And finally, 1 <= jing <= maxjing, 0 <= qi <= 100, 0 <= shen <= maxshen. The last test case is followed by 6 zeros, which should not be processed.

For each test case, print the earliest time that you can win, and all possible orderings to achieve this. Each ordering is expressed as the concatenation of the first letters of H1, H2 and H3's names. For example, if H1=HLS, H2=LML, H3=YTH, the ordering is expressed as HLY. The orderings should be sorted in increasing order lexicographically. If you can't win the combat within 12 units of ball-moving time, print -1. Print a blank line after the output of each test case.

1000 1 1 200 15 75
1000 100 1 2000 2000 2000 2000 300 800 20 0 5 5
900 10 100
1000 100 1 2000 2000 2000 2000 120 300 10 0 5 5
100 80 100
1000 100 1 2000 2000 2000 2000 100 400 30 1 5 5
450 40 100
1000 100 1 2000 2000 2000 2000 250 700 10 1 5 5
600 50 100
3000 4 1 800 15 75
2000 100 3 2 2 2 2 1 1 1 0 2 1 1000 100 100
2000 100 4 2 2 2 2 1 1000 25 0 2 1 1 1 100
2000 100 1 2 2 2 2 1 1000 1 1 1 1 300 100 0
2000 100 3 2 2 2 2 1 1000 30 0 5 1 1 6 100
26399 3 2 3182 543 800
4462 353 2 4300 4875 6856 5527 31497 5633 61 0 68
63 4355 0 351
5444 300 3 7682 1037 597 4214 6744 6861 68 0 65 12
2136 32 143
5875 705 2 2097 118 2366 978 14276 24850 48 0 55
70 3562 40 277
6413 33 1 6305 1898 340 5238 13989 25287 25 1 72
34 3176 4 30
0 0 0 0 0 0

Case 1: 4 HLY HYL LHY LYH YHL YLH

Case 2: 12 HML

Case 3: -1

Explanation

In the first sample, you can win the combat just after one action for each hero (at time 4, since all the su values are 1), but you need to be careful.

YTH's special-skill attack is powerful (damage=900), but his Qi is not enough (10<20). You can't use HLS's weapon attack, since she'll get defeated by physical
reflection. LML's weapon attack is weak, but she can use her special-skill attack even though she'll get hurt by reflection (her special-skill attack is physical),
since 400<450. For MRZY, his special-skill is physical, and too powerful, so we can't use it, since 700>600.

To summarize, we can use YTH's weapon attack (damage=300), HLS's special-skill attack (damage=300), LML's weapon attack (damage=100) and special-skill
attack (damage=400), and MRZY's weapon attack (damage=250). It's not hard to see, the only possible combination that can finish the combat in the quickest
way is YTH, HLS and LML (use special-skill attack), the ordering is arbitrary. Note that the combat ends immediately after SY is defeated, so don't worry about
the terrible attacks of XX and SY.

In the second sample, YTH is too weak so we ignore him immediately. You can't avoid XX's first attack, which is able to defeat everyone except LML, so LML
seems to be the only possible H1. However, HLS moves before XX, so she can also be H1 if she uses Yu Run in her first action. Unfortunately, MRZY can't be
H1, since he's not quick enough to recover Jing before XX attacks.

All the weapon attacks are too weak, so the best strategy is to accumulate Qi first, then perform the powerful special-skill attacks when possible. LML's su is
too low, but her Qi is enough at startup. All she needs to do is to recover Shen, then recover Jing, and then do the attack (Why so complex? because her
powerful special-skill attack is physical…). Note that SY is only able to attack two heroes before the combat ends, so H3 has one fewer chance to increase Qi
by reflection. Actually, it can be proven that neither HLS nor MRZY can be H3 - if so, they'll be unable to gain enough Qi for their special-skill attacks.

To summarize, HLS can be H1 or H2, LML can be all, while MRZY can only be H1. So the only possible ordering is H1=HLS, H2=MRZY, H3=LML.

In the third sample, it seems that you can defeat SY with HLS's special-skill attack (damage=6861) and LML's specialskill attack (damage=24850). However, LML
needs to recover Jing to avoid being defeated, but her initial Shen is not enough If we changed her initial Shen to 543 (enough for Yu Run), the answer would
become "6 LYH LYM".

2009 Asia Wuhan Regional Contest Hosted by Wuhan University