VM 08 Bài 10 - Bộ lạc

View as PDF

Submit solution


Points: 0.48 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 7/DivBProblem Setter: Khúc Anh Tuấn
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Ngôn ngữ của một bộ lạc cổ xưa chỉ sử dụng hai chữ cái ~a~ và ~b~ để tạo ra các từ có nghĩa. Để tạo thành một câu, người ta sử dụng thêm dấu cách để phân tách các từ. Như vậy mỗi dãy các ký tự ~a~ và ~b~ liên tiếp nhau và không thể mở rộng được về hai bên sẽ tạo thành một từ. Một câu không thể chứa từ vô nghĩa. Người trong bộ lạc quan niệm mỗi từ có một giá trị may mắn. Giá trị may mắn của một câu là tổng giá trị may mắn của các từ trong câu. Bạn được sử dụng tối đa ~x~ ký tự ~a~, ~y~ ký tự ~b~ và ~z~ dấu cách, hãy tạo ra câu có trọng số lớn nhất. Trong trường hợp có nhiều kết quả, hãy in ra câu có thứ tự từ điển nhỏ nhất.

Câu ~s_1~ được gọi là có thứ tự từ điển nhỏ hơn ~s_2~ nếu xâu biểu diễn ~s_1~ nhỏ hơn ~s_2~. Thứ tự từ điển của các ký tự là: dấu cách, ~a~, ~b~.

Input

  • Dòng đầu ghi số ~N~, số từ có nghĩa trong ngôn ngữ. ~(1 \le N \le 50)~.
  • Dòng sau ghi ~3~ số ~x~, ~y~, ~z~ như trong đề bài. ~(0 \le x, y, z \le 50)~.
  • ~N~ dòng sau, mỗi dòng ghi một từ thuộc ngôn ngữ và giá trị của nó, cách nhau bởi một dấu cách. Giá trị của một từ là một số nguyên dương không vượt quá ~50~.

Output

Gồm một dòng duy nhất ghi ra câu có thứ tự từ điển nhỏ nhất tìm được.

Sample Input

4
3 3 1
abb 3
baa 3
aaa 4
bbb 1

Sample Output

abb baa

Comments

Please read the guidelines before commenting.


There are no comments at the moment.