P6593 [YsOI2020] Loyalty Is Lost, So I Shall Die Too

> Loyalty is lost, so I shall die too! It has been long and old; let it go with age. This problem includes HACK testdata, and more HACK testdata is welcome.

Ysuperman’s kindergarten not only focuses on cultural classes and competitive programming classes, but also teaches everyone to develop morally, intellectually, physically, and aesthetically. One weekend, the well-rounded Ysuperman climbed Mount Y. When climbing, Ysuperman did not take the main road for vehicles, but instead took the muddy trail beside it. After walking for a long time, he suddenly found that the way back had become blurry, and in front of him stood a huge rock wall. To his shock, he discovered that the wall actually had writings from the last century! “义已失吾亦死”. Looking at these words, he seemed to feel a special kind of charm. After returning to kindergarten, the excited Ysuperman immediately created other sentences, but found that most of them had lost their charm. After two and a half years of research, TA finally discovered that “义已失吾亦死” actually corresponds to the number string $114514$! With a clearer direction, he decided to study mapping a sentence to a number. A “charming” number must satisfy the following conditions: - In decimal, it is a natural number. - Its digits only contain the three digits $1,4,5$. - It is congruent to $0$ modulo a given constant $p$. Now Ysuperman already has many digits $1,4,5$, with $a_1,a_4,a_5$ of them respectively. Ysuperman wants to form a charming number of length $n$ that is as large as possible. Ysuperman knows that if TA were still a student, TA would surely qualify for the Hydroxyl Program because of this discovery. For TA’s childhood dream, can you help him?

**This problem contains multiple test cases.** There are $T$ test cases. The first line contains $T$. Then for each test case: The first line contains two positive integers $n,p$, representing the length of the charming number Ysuperman wants to form and the given constant $p$. The second line contains three natural numbers $a_1,a_4,a_5$, representing the initial counts of digits that Ysuperman has.

If Ysuperman cannot obtain a charming number, output `-1`. Otherwise, output the maximum charming number Ysuperman can form. A newline is required between two test cases.

### Sample Explanation #### Sample Explanation $1$: In the first test case, you can form $1,4,5$, and the maximum is $5$. In the second test case, you can form $145,155,415,455,515,545$, and the maximum is $545$. In the third test case, you can only form $114514$. ----- ### Constraints To pay tribute to NOI, the problem setter specially prepared a generous partial score table. | Test Point ID | $n$ | $a_1,a_4,a_5$ | $p$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $=1$ | $=0$ | $=1$ | | $2$ | $=2$ | $\le 1$ | $\le 10$ | | $3$ | $=3$ | $\le 3$ | $\le 10$ | | $4$ | $=15$ | $\le 15$ | $\le 10$ | | $5$ | $\le 20$ | $\le 20$ | $\le 20$ | | $6$ | $\le 30$ | $\le 30$ | $\le 30$ | | $7$ | $\le 35$ | $\le 35$ | $\le 35$ | | $8$ | $\le 233$ | $\le 233$ | $\le 2$ | | $9$ | $\le 233$ | $\le 233$ | $\le 2$ | | $10$ | $\le 50$ | $\le 50$ | $\le 64$ | | $11$ | $\le 55$ | $\le 55$ | $\le 64$ | | $12$ | $\le 60$ | $\le 60$ | $\le 64$ | | $13$ | $\le 65$ | $\le 65$ | $\le 64$ | | $14$ | $\le 70$ | $\le 70$ | $\le 64$ | | $15$ | $\le 75$ | $\le 75$ | $\le 64$ | | $16$ | $\le 80$ | $\le 80$ | $\le 64$ | | $17$ | $\le 233$ | Property 1 | $\le 64$ | | $18$ | $\le 233$ | Property 1 | $\le 64$ | | $19$ | $\le 233$ | Property 2 | $\le 64$ | | $20$ | $\le 233$ | Property 2 | $\le 64$ | | $21$ | $\le 233$ | $\le 233$ | $\le 64$ | | $22$ | $\le 233$ | $\le 233$ | $\le 64$ | | $23$ | $\le 233$ | $\le 233$ | $\le 64$ | | $24$ | $\le 233$ | $\le 233$ | $\le 64$ | | $25$ | $\le 233$ | $\le 233$ | $\le 64$ | Property 1: $a_1+a_4+a_5=n$. Property 2: $a_1=a_4=a_5=n$. For $100\%$ of the testdata, it holds that: $0 \le a_1,a_4,a_5 \le 233$. $1 \le n \le 233$. $1 \le p \le 64$. $0 \le T \le 5$. ----- ### Hint If you do not know what a natural number means, Ysuperman provides a link: [link](https://zh.wikipedia.org/zh-hans/%E8%87%AA%E7%84%B6%E6%95%B0). If you do not know what modulo means, Ysuperman provides another link: [link](https://zh.wikipedia.org/zh-hans/%E6%A8%A1%E9%99%A4)。 Translated by ChatGPT 5