#! ruby -Ku
 
def back(s)
	return [0, ''] if s.empty?
	(P - s).inject([Float::INFINITY, nil]) do |min, x|
		t, w = go(s + [x])
		t += @t[x]
		t < min[0] ? [t, x + '← ' + w] : min
	end
end
 
def go(s)
	s.combination(2).inject([Float::INFINITY, nil]) do |min, pair|
		t, w = back(s - pair)
		t += pair.map{|x| @t[x]}.max
		t < min[0] ? [t, pair.join + '→ ' + w] : min
	end
end
 
P = ('A'..'D').to_a
@t = Hash[*P.zip([1, 2, 5, 10]).flatten]
puts (result = go(P))[1]
print result[0], 'minutes'

IyEgcnVieSAtS3UKCmRlZiBiYWNrKHMpCglyZXR1cm4gWzAsICcnXSBpZiBzLmVtcHR5PwoJKFAgLSBzKS5pbmplY3QoW0Zsb2F0OjpJTkZJTklUWSwgbmlsXSkgZG8gfG1pbiwgeHwKCQl0LCB3ID0gZ28ocyArIFt4XSkKCQl0ICs9IEB0W3hdCgkJdCA8IG1pblswXSA/IFt0LCB4ICsgJ+KGkCAnICsgd10gOiBtaW4KCWVuZAplbmQKCmRlZiBnbyhzKQoJcy5jb21iaW5hdGlvbigyKS5pbmplY3QoW0Zsb2F0OjpJTkZJTklUWSwgbmlsXSkgZG8gfG1pbiwgcGFpcnwKCQl0LCB3ID0gYmFjayhzIC0gcGFpcikKCQl0ICs9IHBhaXIubWFwe3x4fCBAdFt4XX0ubWF4CgkJdCA8IG1pblswXSA/IFt0LCBwYWlyLmpvaW4gKyAn4oaSICcgKyB3XSA6IG1pbgoJZW5kCmVuZAoKUCA9ICgnQScuLidEJykudG9fYQpAdCA9IEhhc2hbKlAuemlwKFsxLCAyLCA1LCAxMF0pLmZsYXR0ZW5dCnB1dHMgKHJlc3VsdCA9IGdvKFApKVsxXQpwcmludCByZXN1bHRbMF0sICdtaW51dGVzJw==